From Alternating Labels to a Certificate
To test whether a small graph is bipartite, begin by giving one vertex a label and require each neighbor to have the opposite label. Continue this alternation along edges. If every edge joins unlike labels, the two label classes are a bipartition. If an edge joins vertices with the same label, the conflict is not just evidence of a problem: the search records enough information to exhibit an odd cycle.
All graphs in this tutorial are finite and simple. A path is a sequence of distinct vertices with consecutive vertices adjacent; its length is its number of edges. A cycle is a closed sequence of at least three edges whose vertices are distinct except for the repeated starting vertex. An odd cycle has odd length. A bipartition of \(G=(V,E)\) is a pair of disjoint sets \(X,Y\) whose union is \(V\), such that every edge has one endpoint in each set. Either part may be empty. The two labels used below are just names for membership in \(X\) or \(Y\).
Exploration can be organized with a queue: remove the first vertex in the queue, inspect all its neighbors, and add each as-yet-undiscovered neighbor to the end of the queue with the opposite label. A discovered vertex keeps its original label if it is encountered again. When the queue becomes empty, start again from any still-undiscovered vertex. This restart is essential: an isolated vertex, for example, is never reached from a different component.
Why a Conflict Gives an Odd Cycle
Proof. The parent edges form a tree of discovery: each vertex other than the root has exactly one parent, and repeatedly following parents leads back to the root. In this tree there is a unique path from \(u\) to \(v\). Each parent edge joins unlike labels. Since \(u\) and \(v\) have the same label, the tree path between them has even length: traversing an even number of label changes returns to the starting label.
The conflict edge \(uv\) is not a parent edge, because every parent edge joins unlike labels. Therefore the tree path from \(u\) to \(v\), together with \(uv\), is a cycle: the tree path has no repeated vertices, and adding an edge not in the tree closes it. Its length is the even length of the tree path plus one, so it is odd. This is the required certificate. \(\square\)
To write down the cycle in practice, list the parent paths from \(u\) and \(v\) back to the root. Their common part includes the route from the root to their last common ancestor. Remove that shared route from the two paths, join the remaining branches at the common ancestor, and close the resulting tree path with \(uv\). The next example carries out this reconstruction explicitly.
Proof. If the search finishes without a conflict, put all vertices with the first label in \(X\), and all vertices with the second label in \(Y\). Every edge has been checked: an edge first encountered while processing one endpoint either discovers the other endpoint with the opposite label or finds that it already has the opposite label. Thus every edge crosses between \(X\) and \(Y\), so these sets are a bipartition.
If the search finds a conflict, the Lemma supplies an odd cycle. A bipartite graph cannot contain an odd cycle: around any cycle, labels must alternate at every edge, and after an odd number of changes the final vertex would have the opposite label to the starting vertex even though the closing edge requires unlike labels. Thus a conflict rules out bipartiteness.
Finally, if the graph is bipartite, the search cannot encounter a conflict. In each component, its root receives one of the two labels. Every newly discovered vertex receives the opposite label from its parent. Since each edge in a bipartite graph joins different parts, induction on the order in which vertices are discovered shows that every vertex receives the label of its part, up to swapping the two labels for that component. Hence every checked edge has unlike labels. The search therefore finishes without conflict and returns a bipartition. \(\square\)
Worked Search: A Bipartition
Worked Example: A Graph That Passes the Test
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,13,24,35,46,56\}\). Start at vertex \(1\), assign it label \(X\), and use the order shown in the queue table when inspecting neighbors. A dash means that no vertices remain in the queue.
| Vertex processed | Labels newly assigned | Queue after processing |
|---|---|---|
| 1 | 2:Y, 3:Y | 2, 3 |
| 2 | 4:X | 3, 4 |
| 3 | 5:X | 4, 5 |
| 4 | 6:Y | 5, 6 |
| 5 | None; 6 is already Y | 6 |
| 6 | None | — |
The resulting label classes are \(X=\{1,4,5\}\) and \(Y=\{2,3,6\}\). Check every edge: \(12\) joins \(X\) to \(Y\), \(13\) joins \(X\) to \(Y\), \(24\) joins \(Y\) to \(X\), \(35\) joins \(Y\) to \(X\), \(46\) joins \(X\) to \(Y\), and \(56\) joins \(X\) to \(Y\). There is no conflict, so the displayed sets are a valid bipartition.
Check: Each of the six listed edges has one endpoint in each part, and the two parts are disjoint with union \(\{1,2,3,4,5,6\}\). Thus the partition test verifies the search output directly.
Worked Search: Recovering an Odd Cycle
Worked Example: A Conflict on a 5-Cycle
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45,51\}\). Start at \(1\) with label \(X\). When processing a vertex, inspect its neighbors in increasing order, with the root’s neighbors inspected as \(2\) and then \(5\).
| Vertex processed | Discovery or conflict | Queue after processing |
|---|---|---|
| 1 | Discover 2:Y and 5:Y; parent of each is 1 | 2, 5 |
| 2 | Discover 3:X; parent of 3 is 2 | 5, 3 |
| 5 | Discover 4:X; parent of 4 is 5 | 3, 4 |
| 3 | Edge 34 finds 4 already labeled X: conflict | 4 |
The parent path from \(3\) to the root is \(3,2,1\), and the parent path from \(4\) to the root is \(4,5,1\). Their shared portion is the root \(1\). The tree path between the conflicting vertices is therefore \(3,2,1,5,4\), of length \(4\). Close it with edge \(43\) to obtain the cycle \(3,2,1,5,4,3\), of length \(4+1=5\).
Check: Its consecutive edges are \(32,21,15,54,43\), all in \(E\), and its vertices \(3,2,1,5,4\) are distinct. The length is \(5\), which is odd, so this is an odd-cycle certificate. The same conflict also shows directly that the labels cannot form a bipartition: edge \(34\) has both endpoints labeled \(X\).
Worked Search: Restarting Across Components
Worked Example: Disconnected Pieces and an Isolated Vertex
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5,6,7\}\) and \(E=\{12,23,45,56\}\). Explore from the least-numbered undiscovered vertex each time a queue empties. In each component, give its root label \(X\).
| Search stage | Vertex processed | New labels | Queue after processing |
|---|---|---|---|
| Start at 1 | 1 | 2:Y | 2 |
| Continue | 2 | 3:X | 3 |
| Continue | 3 | None | — |
| Restart at 4 | 4 | 5:Y | 5 |
| Continue | 5 | 6:X | 6 |
| Continue | 6 | None | — |
| Restart at 7 | 7 | None | — |
Combining the labels gives \(X=\{1,3,4,6,7\}\) and \(Y=\{2,5\}\). The edge checks are \(12\), from \(X\) to \(Y\); \(23\), from \(Y\) to \(X\); \(45\), from \(X\) to \(Y\); and \(56\), from \(Y\) to \(X\). Vertex \(7\) is isolated, so it contributes no edge condition and may be placed in either part.
Check: The parts are disjoint and together contain all seven vertices. Each of the four edges crosses between them, so the output is a bipartition. The second and third searches matter: starting only at \(1\) would not assign labels to vertices \(4,5,6,7\).
Common Pitfalls and Practical Checks
Do not recolor an already discovered vertex to erase a conflict. For example, in the 5-cycle above, the edge \(34\) joins two vertices labeled \(X\). Changing the label of \(4\) to \(Y\) would fix edge \(34\), but then edge \(45\) would join \(Y\) to \(Y\), because \(5\) was already labeled \(Y\). The recorded parent edges explain why the conflict cannot be repaired by an isolated label change: they give the odd cycle \(3,2,1,5,4,3\).
A partial success is not a certificate. Finding no conflict among the edges inspected so far does not show that the whole graph is bipartite. Finish the queue and restart from every undiscovered vertex. To certify success, give both parts and check every edge. To certify failure, give the vertices of an actual odd cycle in order and verify that its edges are present.
Keep labels and the partition distinct from the certificate. The two labels record the attempted alternation. A valid bipartition requires every edge to cross the final parts. An odd-cycle certificate, by contrast, is a specific cyclic sequence of distinct vertices with all consecutive and closing edges present. The conflict edge and parent records provide that sequence, rather than merely asserting that one exists.
Check Your Understanding
For each search, record the labels and parent edges as needed; verify any proposed partition or cycle against the stated edge set.
- Apply the queue search to \(V=\{a,b,c,d\}\), \(E=\{ab,ac,bd\}\), starting at \(a\). Give a bipartition and check every edge.
- For \(V=\{1,2,3,4\}\), \(E=\{12,23,34,41,13\}\), start at \(1\). Identify a conflict and use parent edges to produce an odd-cycle certificate.
- Why must the search restart when the queue empties? Use a graph with an isolated vertex to illustrate what would be omitted otherwise.
- Prove that every edge in the parent tree joins unlike labels.
- Give an example of a graph with an odd cycle and an even cycle, and explain which one is sufficient to rule out a bipartition.