# About a strongly connected directed graph.

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?

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.