# Prove that every strongly connected digraph has an odd directed cycle if its underlying graph has an odd cycle

Let D be a strongly connected digraph. Prove that if its underlying graph has an odd cycle, then D has an odd directed cycle.

My first approach would be to assume that D has not such a cycle and then exhibit that D is weakly connected. But I'm not going anywhere with the construction of D. Any ideas?

I've come to a solution somewhat simpler.

Let D be a strongly connected digraph. Let $C = v_1 v_2 ... v_m$, $v_m = v_1$, be an odd cycle in the underlying graph. For each i, from 1 to m-1, let $W_i$ be a minimal walk from $v_i$ to $v_{i+1}$. If both vertices are connected by an edge $e_i = v_iv_{i+1}$, then $W_i = v_ie_iv_{i+1}$. Else, if the edge is $v_{i+1}v_i$, then suppose $W_i$ is an odd length walk (otherwise, we'd have an odd length cycle and be done by now). Since m-1 is odd, we have constructed an odd number of odd length walks. Concatenating them as $W_0 . W_1 . ... W_{m-1}$, we have a closed odd walk. Since every closed odd walk has a closed odd cycle, we're done.

Suppose $D$ has no odd directed cycle.

We try to colour the vertices black and white, such that the the neighbours of a white vertex is a black vertex and vice versa. As the graph is strongly connected, every vertex's colour can be deduced from any initial source vertex $s$ as there exists a path from the initial vertex to any other vertex.

Suppose two vertices $u, v$ are the same colour. If they are connected by an edge, we consider the paths from the source vertex $s$ to the two ends of that edge which are used to determine the colour of the two vertices. Since the two vertices are of the same colour, the parity of the lengths of the 2 paths must be the same. We denote the two paths by $s\Rightarrow u$ and $s\Rightarrow v$.

Let the directed edge be denoted $u\rightarrow v$. Consider the path from $s\Rightarrow v$ and we choose a path from $v$ to $s$ to continue with. A path from $v$ to $s$ always exists as the graph is strongly connected.

Since there are no odd cycles, the sum of the lengths of these two paths must be even so that the two paths form an even cycle. The length of the path from $v$ to $s$ must have the same parity as the length of $s\Rightarrow v$, which is the same parity as the length of $s\Rightarrow u$.

Consider the cycle $s\Rightarrow u\rightarrow v$ to $s$. It has an odd number of edges. Contradiction. Our assumption of two vertices the same colour connected by an edge is thus wrong. Hence the underlying graph is bipartite (since the colouring we have assigned does not produce the problem of having 2 vertices of the same colour connected), and a property of bipartite graphs, the underlying graph has no odd cycle.

By contrapositive, we prove that if the underlying graph has an odd cycle, then $D$ has an odd cycle.

• I'm not sure if I followed it. If the underlying graph is not bipartite, D will not be as well, that's fine. But it's easy to find a digraph D, not bipartite, with no odd directed cycle. Commented Nov 18, 2015 at 14:50
• @gcolucci How would you suggest to find that digraph? Commented Nov 18, 2015 at 14:52
• For instance, consider 3 vertices, a, b and c, and the following edges: a->b, b->c, a->c. It's not bipartite, since it's underlying graph is an odd cycle, but it has no directed cycle. Commented Nov 18, 2015 at 14:56
• @gcolucci Fixed. Commented Nov 18, 2015 at 15:27
• why does that hold: "Since there are no odd cycles, the sum of the lengths of these two paths must be even"? Commented Nov 18, 2015 at 21:33