A robot starts at a node of a fully connected graph of 5 nodes (shown below). Each turn the robot can move across an edge and paint it in one of two colours - blue for odd turns and red for even turns. The robot can revisit nodes and edges, and it can repaint already painted edges. What is the most number of edges that can be painted in blue at any given point in time?
Image from Wikipedia
We can paint this many edges blue:
9 (out of 10) (This is only possible if we can immediately revisit the edge we just used in reverse, which doesn't seem to be forbidden.)
As follows:
Say we start at B. The first edge will be blue.
B -> A
AB is blue. Now the next edge will be red.
A -> C -> A -> D -> A -> E
AC and AD are blue. The next edge will be blue.
E -> B -> D -> B -> C -> E
BD, BE, and CE are blue. The next edge will be red.
E -> A -> E -> D
AE changed from red to blue. The next edge will be blue.
D -> C -> B -> C
BC changed from red to blue; CD is now blue. All edges are now blue except DE (which is red).
Why we can't do better:
If we could get 10 blue edges, the last edge we painted must have been blue. Then, looking backward, consider the most recent visit to another vertex without having immediately returned to the final vertex. (There must be such a vertex because the final vertex isn't adjacent to all edges and we must have visited all edges.) On the occasion of that visit, the last edge we painted must have been red. But, since we have didn't immediately return to the final vertex, that previous red edge must still be red since it isn't adjacent to the final vertex and we can't have revisited it since then.
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.
Proof:
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.
