I came up with a proof of

Graph $G$ has no cycles of odd length $\implies$ $G$ is bipartite.

like this:

Without loss of generality, let's only consider a connected component, because if every connected component of a graph is bipartite, then the whole graph is bipartite.

Pick up a random vertex $v$ in $G$, calculate the length of the shortest simple path from $v$ to any other node, call this value distance from $v$, and divide nodes into 2 groups according to the parity of their distance to $v$. If we can prove that nodes belong to the same group can not be adjacent, then we know that we actually get a partition of the $G$ that fulfill the definition of bipartite graph.

Now, to introduce contradiction, assume two nodes $x, y$ with both even or odd distance from $v$ are adjacent, then the shortest simple path $\langle v, x \rangle$, $\langle v, y \rangle$ and edge $\{x, y\}$ contains a cycle with odd length, which is contradictory to that $G$ has no cycles of odd length. In other words, nodes both with even or odd distance from $v$ can not be adjacent, which is exactly what we need.

So my question is, is my proof correct? And is there simpler method to prove the proposition?


(to address comment from Srivatsan Narayanan)

To prove that $\langle v, x \rangle$ and $\langle v, y \rangle$, together with $\langle x, y \rangle$ contains a cycle with odd length is obvious when $\langle v, x \rangle$ and $\langle v, y\rangle$ are disjoint. When that's not the case, let's give the last node shared by $\langle v, x\rangle$ and $\langle v, y\rangle$ the name $v'$. So the three nodes $v', x, y$ forms a cycle with length $\newcommand{\len}{\operatorname{len}}$

$$ L = \len(\langle v', x \rangle) + \len(\langle v', y \rangle) + 1 = \len(\langle v, x \rangle) + \len( \langle v, y \rangle) - 2 \cdot \len(\langle v, v'\rangle) + 1 .$$

where $\len()$ means the length of the shortest path.

As $\len(\langle v, x \rangle)$ and $\len(\langle v , y \rangle)$ are both even or odd, then $L$ must be odd. Therefore, in both cases, disjoint or not, $\langle v, x \rangle$, $\langle v, y \rangle$ and $\langle x, y\rangle$ contains a cycle with odd length.


To see $\len(\langle v, x \rangle) = \len(\langle v, v'\rangle) + \len(\langle v', x \rangle)$, we can simply prove that both $\langle v, v' \rangle$ and $\langle v', x \rangle$ are both shortest path. And that's obvious, because if it's not the case, there exist a path shorter than $\langle v, v' \rangle$ from $v$ to $v'$, or there exist a path shorter than $\langle v', x\rangle$ from $v'$ to $x$, then $\langle v, x \rangle$ can not be a shortest path.

  • 3
    $\begingroup$ You will need to argue that the shortest paths from $v$ to $x$ and $y$, together with the edge $xy$, forms an odd cycle more carefully. This is clear when the shortest paths are disjoint; what would happen otherwise? (Also, a typo: your very first line should read connected graph, not a path.) $\endgroup$ – Srivatsan Sep 4 '11 at 22:38
  • 3
    $\begingroup$ Also: it should be "if every connected component", not "if any connected component" (I would understand the latter as saying that if at least one connected component is bipartite, then the graph is bipartite, that is clearly not what you mean to say). $\endgroup$ – Arturo Magidin Sep 4 '11 at 22:47
  • 1
    $\begingroup$ @ablmf: I don't think you are addressing Srivatsan's comment: just saying that the paths from $v$ to $x$, from $v$ to $y$, and the edge $[x,y]$ "contains a cycle of odd length" is not very informative. It's reasonably clear that they contain a cycle, and that if the paths $v\to x$ and $v\to y$ are disjoint, then the cycle will be of odd length; but you have to prove that it contains a cycle of odd length even if the paths are not disjoint, and that is not quite so obvious that you can get away with not saying anything about it. $\endgroup$ – Arturo Magidin Sep 5 '11 at 1:15
  • 1
    $\begingroup$ @ablmf I think that should do. One more nitpick: You still must justify that the distances from $v$ to $v'$ along the paths $\langle v, x \rangle$ and $\langle v,y \rangle$ are both equal to $len(v,v')$, the shortest distance from $v$ and $v'$. $\endgroup$ – Srivatsan Sep 5 '11 at 1:36
  • $\begingroup$ Thanks! This is my first proof on math.stackexchange.com Although it's answering my own question. $\endgroup$ – ablmf Sep 5 '11 at 1:40

I believe the question is resolved to the satisfaction of the OP. See the comments and the revisions to the question for the relevant discussions.$\newcommand{\len}{\operatorname{len}}$

Here I present a different, and--in my mind--conceptually cleaner proof of the same fact.

Assume $G$ is a connected graph such that all of whose cycles are of even length. We generalize this slightly to the following

Proposition. Any closed walk in $G$ has even length.

Proof. Towards a contradiction, suppose not. Let $W$ be a closed walk of odd length such that the length of $W$ is as small as possible. By hypothesis, $W$ cannot be a cycle; i.e., $W$ visits some intermediate vertex at least twice. Hence we can write $W$ as the "concatenation" of two non-trivial closed walks $W_1$ and $W_2$, each of which is shorter than $W$. Further, $\len W_1 + \len W_2 = \len W$, which is odd. Thus at least one of $W_1$ and $W_2$ is of odd length, contradicting the minimality of $W$. Thus there cannot be any closed walk in $G$ of odd length. $\quad\quad \Box$

Partitioning the graph into even and odd vertices. Now, fix a vertex $v$, and define $E$ (resp. $O$) be the set of vertices $x$ in $G$ such that there is an even-length (resp. odd-length) walk from $v$ to $x$. The sets $E$ and $O$ partition $V$:

  • Assuming $G$ is connected, then clearly $E \cup O = V$.

  • We now show that $E \cap O = \emptyset$. To the contrary, suppose $x$ is in both $E$ and $O$. Then there is a $v$-$x$ walk $W_1$ of even length and another one $W_2$ of odd length. Then the walk $W_1 \circ \operatorname{reverse} (W_2)$ is a closed walk in $G$ of odd length, a contradiction.

Finally, we show that every edge crosses the cut $(E, O)$:

  • Assume $x \in E$ and $xy$ is an edge. Then there exists a $v$-$x$ walk $W$ of even length. Therefore, $W \circ xy$ is a $v$-$y$ walk and it has odd length. Therefore, $y \in O$.

  • Similarly, if $x \in O$ and $xy$ is an edge, we can show that $y$ is in $E$. This proof is similar to the above case.

This establishes that $G$ is bipartite, as desired.


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.