Two Possible Outputs
A BFS two-coloring test has a useful feature: it can return more than a yes-or-no answer. If the graph is bipartite, the test produces two parts and every edge can be checked to cross between them. If the graph is not bipartite, it can produce a specific odd cycle. The cycle is a certificate of failure: its edges can be listed and checked without rerunning the search.
Throughout, \(G=(V,E)\) is a finite simple undirected graph. A path is a sequence of distinct vertices with consecutive vertices adjacent. A cycle is a closed sequence of at least three edges whose vertices are distinct except that the first and last are the same. Its length is its number of edges. A bipartition is a division of \(V\) into sets \(X\) and \(Y\) such that every edge has one endpoint in each set. Either set may be empty.
The parent edges form a tree within each component searched. Consequently, following parent pointers from a vertex back to the root gives a path of length \(d(r,v)\). In a disconnected graph, one BFS does not reach every vertex: restart from an unvisited vertex until all components have been searched. An isolated vertex starts and finishes a component by itself.
The Test and the Certificate
Run BFS in each component, assigning each vertex the parity color of its distance from that component's root. Afterward, inspect every edge. If every edge has endpoints of opposite colors, the color classes give a bipartition. If some edge \(uv\) has endpoints of the same color, use the BFS parent paths to reconstruct a cycle.
Let \(w\) be the last common vertex on the parent paths from the root to \(u\) and \(v\). The paths from \(w\) to \(u\) and from \(w\) to \(v\) have no common vertices other than \(w\). Join these two paths using the conflicting edge \(uv\). The result is the odd-cycle certificate. The last common vertex matters: the full root-to-\(u\) and root-to-\(v\) paths may share a long initial section, which must not be included in the cycle.
Start a BFS at an unvisited vertex. Record each newly discovered vertex's parent and distance. Continue until the queue is empty, then restart if any vertex remains unvisited.
Give each even-distance vertex one color and each odd-distance vertex the other. A parent-child pair always receives opposite colors.
If every edge crosses the color classes, return those classes. Otherwise choose an edge \(uv\) whose endpoints have the same color.
Follow parent pointers to find the last common vertex \(w\). Take the tree path from \(w\) to \(u\), the edge \(uv\), and the tree path from \(v\) back to \(w\).
Why the Certificate Is Correct
Proof. First suppose the test finds no conflicting edge. Let \(X\) be the vertices with even distance from their component roots, and let \(Y\) be those with odd distance. Every vertex is reached because the search is restarted in every component. By the edge check, each edge has endpoints in opposite classes, so \(X,Y\) form a bipartition.
Now suppose the test finds a conflicting edge \(uv\). The two endpoints have distances of the same parity. Their parent paths from their root share an initial segment; let \(w\) be the last vertex on that shared segment. After \(w\), the paths to \(u\) and \(v\) are internally disjoint. The edge \(uv\) is not a parent edge, because a parent and child have distances differing by one. Thus the two paths together with \(uv\) form a simple cycle. Its length is \[ (d(r,u)-d(r,w))+(d(r,v)-d(r,w))+1. \] Since \(d(r,u)\) and \(d(r,v)\) have the same parity, the sum of the first two terms is even; adding one makes the cycle length odd. The cycle has at least three edges: if the tree path from \(u\) to \(v\) had length one, \(uv\) would be a parent edge. Thus the output is a simple odd cycle.
It remains to show that a bipartite graph cannot produce a conflict. In any component, choose a root. Along every path from the root, the vertices alternate between the two parts of a bipartition. Therefore a vertex's distance parity determines which part it belongs to: every path from the root to that vertex has the same parity, since each step switches parts. The endpoints of every edge lie in opposite parts and so have opposite distance parities. No edge can be a conflict. Together, these arguments show that success is equivalent to bipartiteness, and that failure produces the stated certificate. \(\square\)
Worked Traces
Worked Example: A Triangle Found at the First Conflict
Let \(V=\{1,2,3,4,5\}\) and \(E=\{12,13,23,34,45\}\). Start BFS at \(1\), process neighbors in increasing order, and check the edges after the search. The queue records the vertices waiting to be processed.
| Action | Queue afterward | New labels and parents |
|---|---|---|
| Initialize at \(1\) | \([1]\) | \(d(1,1)=0\) |
| Process \(1\) | \([2,3]\) | \(d(1,2)=1,\ p(2)=1;\ d(1,3)=1,\ p(3)=1\) |
| Process \(2\) | \([3]\) | \(3\) is already discovered |
| Process \(3\) | \([4]\) | \(d(1,4)=2,\ p(4)=3\) |
| Process \(4\) | \([5]\) | \(d(1,5)=3,\ p(5)=4\) |
| Process \(5\) | \([]\) | No new vertex |
Vertices \(2\) and \(3\) both have distance \(1\), so they have the same color. The edge \(23\) is a conflict. Their parent paths are \(1,2\) and \(1,3\), with last common vertex \(1\). Joining the paths by \(23\) gives the cycle \(1,2,3,1\), of length \(1+1+1=3\).
Check: Its edges \(12,23,31\) are all in \(E\); its vertices \(1,2,3\) are distinct; and its length \(3\) is odd. Thus the output is a valid certificate that this graph is not bipartite.
Worked Example: Reconstructing a Longer Odd Cycle
Let \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45,51\}\). Start at \(1\) and process neighbors in increasing order.
| Action | Queue afterward | New labels and parents |
|---|---|---|
| Initialize at \(1\) | \([1]\) | \(d(1,1)=0\) |
| Process \(1\) | \([2,5]\) | \(d(1,2)=1,\ p(2)=1;\ d(1,5)=1,\ p(5)=1\) |
| Process \(2\) | \([5,3]\) | \(d(1,3)=2,\ p(3)=2\) |
| Process \(5\) | \([3,4]\) | \(d(1,4)=2,\ p(4)=5\) |
| Process \(3\) | \([4]\) | No new vertex |
| Process \(4\) | \([]\) | No new vertex |
The edge \(34\) has endpoints both at distance \(2\), so it is a conflict. The parent paths are \(1,2,3\) and \(1,5,4\); their last common vertex is \(1\). The tree path from \(3\) to \(4\) through \(1\) is \(3,2,1,5,4\). Adding \(34\) closes the cycle \(1,2,3,4,5,1\), whose length is \(2+1+2=5\).
Check: The cycle uses the edges \(12,23,34,45,51\), exactly the five edges of \(E\). Its vertices \(1,2,3,4,5\) are distinct before returning to \(1\), and \(5\) is odd.
Worked Example: A Bipartition Across Disconnected Components
Let \(V=\{1,2,3,4,5,6,7\}\) and \(E=\{12,14,23,34,56\}\). The graph has a component on \(\{1,2,3,4\}\), a component on \(\{5,6\}\), and the isolated vertex \(7\). Search components in increasing order, processing neighbors in increasing order.
| Action | Queue afterward | New labels and parents |
|---|---|---|
| Start at \(1\) | \([1]\) | \(d(1,1)=0\) |
| Process \(1\) | \([2,4]\) | \(d(1,2)=d(1,4)=1\) |
| Process \(2\) | \([4,3]\) | \(d(1,3)=2,\ p(3)=2\) |
| Process \(4\) | \([3]\) | \(3\) is already discovered |
| Process \(3\) | \([]\) | No new vertex |
| Restart at \(5\); process \(5\) | \([6]\) | \(d(5,5)=0;\ d(5,6)=1,\ p(6)=5\) |
| Process \(6\) | \([]\) | No new vertex |
| Restart at \(7\); process \(7\) | \([]\) | \(d(7,7)=0\) |
The even-distance class is \(X=\{1,3,5,7\}\), and the odd-distance class is \(Y=\{2,4,6\}\). Check each edge: \(12\) joins \(X\) to \(Y\); \(14\) joins \(X\) to \(Y\); \(23\) joins \(Y\) to \(X\); \(34\) joins \(X\) to \(Y\); and \(56\) joins \(X\) to \(Y\). Every edge crosses, so the classes certify bipartiteness. The isolated vertex \(7\) causes no difficulty: it belongs to \(X\) and has no incident edge to check.
Check: The first component has the 4-cycle \(1,2,3,4,1\), which has even length. The only other edge is \(56\), and vertex \(7\) is isolated. The listed classes account for all seven vertices and every edge.
Common Pitfall: Keep Only the Cycle, Not the Shared Stem
Suppose \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45,53\}\), with BFS rooted at \(1\). The parent paths to \(4\) and \(5\) are \(1,2,3,4\) and \(1,2,3,5\). Both endpoints have distance \(3\), and \(45\) is a conflict. A tempting but incorrect reconstruction is to concatenate the full paths and the conflict edge, producing the closed walk \(1,2,3,4,5,3,2,1\). This repeats vertices, so it is not a cycle. The correction is to remove the shared stem \(1,2,3\): the last common vertex is \(3\), and the actual certificate is \(3,4,5,3\). Its edges \(34,45,53\) are present, and its length is \(3\), which is odd.
When checking an output, use the right standard for its type. A bipartition is verified by checking every edge. An odd-cycle certificate is verified by checking that consecutive vertices are adjacent, that the cycle has no repeated vertices other than its closing vertex, and that its length is odd. The BFS search supplies the parent data for constructing a certificate; the final check makes explicit what the output establishes.
Check Your Understanding
For each question, track components separately and distinguish a parent path from the cycle formed by two paths and a conflicting edge.
- Let \(V=\{1,2,3,4\}\) and \(E=\{12,23,34,41\}\). Run BFS from \(1\), record the parent paths, and give a bipartition.
- Let \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,23,31,45\}\). What happens when the search restarts at \(4\)? Identify an odd-cycle certificate, if one is found.
- Why must a conflicting edge have endpoints that are not parent and child in the BFS tree?
- In the shared-stem example, why is \(3,4,5,3\) a cycle but \(1,2,3,4,5,3,2,1\) not a cycle?
- Explain why a successful test must check every edge, not just the edges used to discover new vertices.