After seeing tehtmi's correct answer, I wanted to find a more general solving method.
Here is a method/proof that works for any connected graph with a cycle of length 3, which paints everything blue except for
one red edge in the 3-cycle.
Move the robot to the 3-cycle.
Of all the nodes that still have one or more red edges, find one which is furthest from the 3-cycle (counted in number of edge traversals needed to get there). If there are several at equal maximal distance, choose any one of them.
Imagine that the robot takes the shortest path to the chosen node. If the next move after that would be red, then indeed take that path. Otherwise go around the 3-cycle first, and then go down the path. Either way, the robot is at the chosen node and the next move will be red.
If any adjacent edge is red, traverse it twice to turn it blue. So now all the node's edges are blue.
Go back along the path (which makes the exiting edge red again), around the cycle, and then forwards and backwards along the path again (painting that edge blue). This makes all the chosen node's edges blue and brings the robot back to the cycle.
Repeat the above steps until everything but the 3-cycle is blue.
Move around the 3-cycle until two of its edges are blue, one red.
Below is my initial answer, which wrongly assumed that the robot cannot turn around and immediately repaint the edge it came from.
I'll call all non-blue edges red (i.e. unpainted edges are also called red).
This answer depends on the following insight:
If a node does not have the robot currently visiting it, then that node must have at least one red edge. This is because any previous visit of the robot to that node must have left a red edge - either the edge the robot took to reach the node or the edge it took when it left.
(Edit: The above uses that incorrect implicit assumption that the incoming and outgoing edges must be different.)
Think of the graph as being split into an outer ring and five diagonal edges.
Let the robot go around the outer ring. If the next colour the robot will paint is blue, and the current node has a red diagonal, then let the robot paint the diagonal blue. In short, go around the ring except when you can paint a red diagonal blue.
Eventually all the diagonals will be blue. The outer ring has an odd length so for any red diagonal the robot will eventually land on one of the end nodes on an even turn.
Once all the diagonals are blue, go around the outer ring until three of them have been painted blue.
This leaves only two red edges, and from the earlier insight, that must be optimal.