About a strongly connected directed graph.

Question

Prove that the following two conditions for a strongly connected directed graph G are equivalent:

(i)G contains a directed cycle of an even length.

(ii) The vertices of G can be colored by 2 colors (each vertex receives one color) in such a way that for each vertex u there exists a directed edge (u, v)with v having the color different from the color of u.

It is probably easy to prove (i)$\Leftarrow$(ii). In short, Assuming the vertex colors are white and black,since it passes through the white and black vertices alternately, G contains a directed cycle of an even length.Is it alright?

But, proof of (i) $\Rightarrow$(ii) is difficult.Please give me your advise if you have any ideas.

By the way, is the equivalence not true in weakly connected?If so why?

Answer 1

Color an arbitrary even cycle in a legal way (alternate bewteen colors as you go through the cycle), and then choose arbitrary paths of uncolored vertices that end in a colored vertex and color them in a legal way that matches the vertex they end on, until all vertices are colored. all colored vertices satisfy your rule due to our construction, and all vertices will be colored because the graph is strongly connected so there is always a path from an uncolored vertex towards a colored vertex.

this does not work for weakly connected since a vertex might have an out-degree of zero, which makes it impossible to satisfy the rule.

Answer 2

The core of your argument for (ii)->(i) is sound, but it should be more rigorous. The pattern you describe could be used to create a color-alternating directed walk of arbitrary length. Since the graph has a finite number of vertices, a sufficiently long directed walk would have to repeat a vertex, and from there you could create a directed cycle (which, as you constructed it, would have to have even length).

For (i)->(ii), since the digraph has a directed even cycle, it has one of minimum length. Let $v$ be any vertex on the cycle. Color each vertex of the digraph white if its distance (i.e. the number of edges in a shortest directed path) to $v$ is even, and black if its distance to $v$ is odd. For any vertex that is not $v$ there is clearly an out-neighbor whose vertex is the opposite color (i.e. the "next" vertex in the shortest directed path to $v$). The same is true of $v$, since the "next" vertex along the directed cycle must be black.

Does this work for a weakly-directed digraph? Well, this strategy would certainly need to have a vertex that was reachable by all other vertices that also had an outneighbor. So strong-directedness is sufficient but not necessary.