digraph: cycle of an even length and coloring the vertices

ry.

Apr 2010
1
0
Prove that the following two conditions for a strongly connected directed graph G are equivalent:
1. G contains a directed cycle of an even length.
2. 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.