5
$\begingroup$

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?

enter image description here

Image from Wikipedia

$\endgroup$
0

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Yep you got it! Nice proof of optimality. For fun you may want to consider what happens for the general $K_n$ graph. $\endgroup$ Jul 11 at 6:04
4
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ The insight is not true if those two edges are the same edge (which doesn't seem to be explicitly forbidden...) $\endgroup$
    – tehtmi
    Jul 11 at 5:56
  • $\begingroup$ @tehtmi Indeed, it seems I did unwittingly make that assumption. $\endgroup$ Jul 11 at 5:58
  • $\begingroup$ The robot can turn around and immediately repaint the same edge. It's not forbidden. $\endgroup$ Jul 11 at 6:02
  • $\begingroup$ Very nice generalization. I assume this works if there are multiple 3-cycles? $\endgroup$ Jul 12 at 12:40
  • 1
    $\begingroup$ @DmitryKamenetsky Yes, just pick one of the 3-cycles and ignore the rest. The result may take many more moves than necessary when you do that. You can actually let the robot go around any odd cycle to change the parity, as long as that cycle does not involve vertices that you have previously turned blue. I do wonder about graphs with only longer cycles, for example the dodecahedron graph. I suspect it is impossible to do better than two red edges there but have no proof. $\endgroup$ Jul 12 at 13:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.