TU Wien:Diskrete Mathematik für Informatik UE (Gittenberger)/Übungen WS13/Beispiel 30

Prove that a graph $G$ is bipartite if and only if each cycle in $G$ has even length.

Solution

G bipartite ⇒ Each cycle in G has even length

Let us assume $G$ is bipartite and there exists a cycle with odd length. Suppose the first node of this cycle belongs to the set $U$, then the second node belongs to set $V$, the third node to set $U$, and so on. But this means that the last node and the first node belong to set the same set $U$ and therefore we know that $G$ is not bipartite.

Each cycle in G has even length ⇒ G bipartite

Let us assume each cycle in $G$ has even length but $G$ is not bipartite. This means that in one of the cycles of $G$ there has to be a node and a neighbour of this node which belong to the same set. Suppose the first node of this cycle belongs to set $V$, then the second node belongs to set $U$, the third node belongs to set $V$, the fourth node belongs to set $U$, and so on. Since all cycles have even length we see that every node and its neighbour node belong to a different set. Therefore G has to be bipartite.

---

Above solution is a bit odd. Here is a better one.