The Bipartite Odd-Cycle Characterization

The Obstruction to a Bipartition

A bipartition divides the vertices of a graph into two parts so that every edge goes from one part to the other. The division can be viewed as assigning two colors, with adjacent vertices required to receive different colors. Following edges in such a graph forces the colors to alternate. A cycle can return to its starting vertex consistently only if its length is even. The converse is less immediate: when every cycle is even, we must show that a suitable two-part division exists.

All graphs in this tutorial are finite and simple: they have no loops or multiple edges. A walk is a sequence of vertices in which consecutive vertices are joined by an edge; vertices and edges may repeat. A walk is closed if its first and last vertices are equal. A path is a walk with no repeated vertices. A cycle is a closed walk of length at least \(3\) whose vertices, other than the repeated first and last vertex, are distinct. The length of a walk is its number of edges.

The equivalence with two-coloring follows by taking \(X\) to be the vertices of one color and \(Y\) the vertices of the other. Conversely, color the vertices in each part with its own color. Isolated vertices cause no difficulty: each can be put in either part because it has no incident edge. The empty graph is bipartite as well, with both parts empty.

Why Bipartite Graphs Have No Odd Cycle

Suppose a cycle lies in a bipartite graph with parts \(X\) and \(Y\). Start at any vertex of the cycle. Each successive edge changes parts, so the cycle's vertices alternate between \(X\) and \(Y\). If its length were odd, after traversing all its edges the walk would end in the opposite part from the one in which it started. But the cycle ends at its starting vertex, which belongs to the same part. Therefore its length must be even.

This argument proves one direction of the characterization: a bipartite graph contains no odd cycle. For the reverse direction, the key is to measure how far each vertex is from a chosen root. We will need a lemma to ensure that a parity conflict in these distances really produces an odd cycle, rather than merely a closed walk with repeated vertices.

Odd Closed Walks Contain Odd Cycles

Proof. We use strong induction on the odd length \(\ell\) of a closed walk \(W=v_0v_1\cdots v_\ell\), where \(v_\ell=v_0\). A closed walk of length \(1\) would use a loop, which a simple graph does not have. Thus \(\ell\geq 3\). If \(v_0,\ldots,v_{\ell-1}\) are distinct, then \(W\) is itself a cycle of odd length, as required.

Otherwise, some vertex is repeated among \(v_0,\ldots,v_{\ell-1}\). Choose indices \(i,j\) with \(0\leq i<j\leq \ell-1\) and \(v_i=v_j\). The segment \(v_i v_{i+1}\cdots v_j\) is a closed walk of length \(j-i\). The rest of \(W\), followed from \(v_j\) back around to \(v_i\), is another closed walk, of length \(\ell-(j-i)\). Both lengths are positive and smaller than \(\ell\), and their sum is \(\ell\), which is odd. Hence one of the two lengths is odd. That odd-length closed walk cannot have length \(1\), since the graph has no loops. The induction hypothesis applies to it and gives an odd cycle. Its edges occur in \(W\), so \(W\) contains that odd cycle. \(\square\)

The repeated-vertex step is important: a closed walk need not be a cycle. The lemma says that if its length is odd, repetitions can be removed until an odd cycle is found.

The Bipartite Odd-Cycle Characterization

Proof. First suppose \(G\) is bipartite. As shown above, traversing a cycle alternates between the two parts. Returning to the starting vertex requires an even number of changes of part, so every cycle has even length. Thus \(G\) has no odd cycle.

Now suppose \(G\) has no odd cycle. We construct a bipartition separately within each connected component. A connected component is a maximal set of vertices in which every pair is joined by a path; an isolated vertex is a component by itself. There are no edges between distinct components, so bipartitions of the components can be combined.

Consider one component and choose a root vertex \(r\). For each vertex \(v\) in this component, let \(d(r,v)\) be the length of a shortest path from \(r\) to \(v\). Such a path exists by the definition of the component. Put vertices at even distance in \(X\), and vertices at odd distance in \(Y\). These sets partition the component, since each distance is a nonnegative integer.

We claim that every edge joins vertices at distances of opposite parity. Suppose instead that an edge \(uv\) has endpoints whose distances from \(r\) have the same parity. Choose a shortest path from \(r\) to \(u\), of length \(d(r,u)\), and a shortest path from \(r\) to \(v\), of length \(d(r,v)\). Follow the first path from \(r\) to \(u\), then the edge \(uv\), then the second path backwards from \(v\) to \(r\). This is a closed walk of length

Because \(d(r,u)\) and \(d(r,v)\) have the same parity, their sum is even. Adding \(1\) makes the closed-walk length odd. By the lemma, this closed walk contains an odd cycle, contradicting the assumption on \(G\). Therefore every edge in this component crosses between \(X\) and \(Y\), making the component bipartite. Combining the partitions over all components gives a bipartition of \(G\). If \(G\) has no vertices, the empty partition already works. This proves the reverse direction and the theorem. \(\square\)

Worked Examples

Using the Characterization Carefully

The two directions serve different purposes. To prove that a graph is not bipartite, it is enough to exhibit one odd cycle. To prove that it is bipartite, it is not enough to point out that some visible cycles are even: one must establish a bipartition, or establish that no odd cycle exists. The theorem is a global statement about all cycles in the graph.

A useful way to understand the reverse direction is through parity. Within a connected component, shortest-path distance from a root assigns each vertex an even or odd label. If an edge joined two vertices with the same label parity, the two root paths and that edge would create an odd closed walk. The lemma then turns that walk into an odd cycle. When no odd cycle exists, every edge must cross between the two parity classes.

Common mistake. A common incorrect argument says, “The graph has an even cycle, so it is bipartite.” For example, the graph \(V=\{1,2,3,4,5\}\), \(E=\{12,23,34,41,15,52\}\) contains the even cycle \(1,2,3,4,1\), but also contains the triangle \(1,5,2,1\). The triangle has length \(3\), so the graph is not bipartite. Having an even cycle does not rule out a different odd cycle; the correct test concerns whether there is any odd cycle at all.