Two types with incompatible pairs
Suppose each vertex is to receive one of two colors, and every edge joins different colors. This can represent separating conflicting tasks into two groups.
Definition 1.2.1
(Bipartite graph)
A graph for which such a coloring exists is bipartite: its two color classes form a partition, including an empty class when appropriate.
We consider finite undirected simple graphs, including disconnected graphs and isolated vertices. A cycle has at least three distinct vertices, apart from its repeated starting vertex.
The odd-cycle criterion
Theorem 1.2.2
(Bipartite if and only if no odd cycle)
A finite undirected simple graph is bipartite exactly when it contains no cycle of odd length.
Proof
(Alternation, and tree-distance parity)
If a proper two-coloring exists, walking along an edge switches colors. Returning to the starting color after a cycle therefore takes an even number of switches, so every cycle has even length.
For the converse, work separately in each connected component. Choose a root and a breadth-first search tree. Color each vertex by the parity of its tree distance from the root. Suppose an edge joins vertices of the same color. The unique tree path from to has even length: if is their lowest common ancestor, that length is . The edge is not a tree edge, since tree edges join opposite depth parities. Adding it to the simple tree path gives an odd cycle. Hence when no odd cycle exists, no edge can join equal colors, and the coloring is proper. An isolated root gets either color.
Proof X-ray
A failed edge produces a concrete witness
The two root-to-vertex paths can share an initial segment, so simply joining both full paths and the edge may repeat vertices. Remove their common part and use the unique tree path through the lowest common ancestor instead. It is simple, has even length when endpoint parities agree, and together with the non-tree edge forms an odd cycle. This explains both the parity and the simplicity of the certificate.
An algorithm and its output
Run breadth-first search from an uncolored vertex, color it zero, and assign each newly discovered neighbor the opposite color. When an examined edge has equally colored endpoints, output the odd cycle reconstructed from the two tree paths and that edge. If a component finishes without conflict, start again at any uncolored vertex; if all finish, output the two color classes. With adjacency lists, each vertex and edge is examined a constant number of times, using time and space including the input representation. The parent pointers needed to reconstruct one witness use additional space. The algorithm handles the empty graph by returning two empty classes.
Worked examples
Worked example 1.2.3
(A path and a four-cycle)
For the path , choose as root. Its depth parities give classes and . Every edge crosses them. Adding edge makes a four-cycle and this coloring still works.
Worked example 1.2.4
(A triangle gives the shortest witness)
For the triangle with edges , root at . Breadth-first search can make both and children of , so they receive the same color. The edge is a conflict; the tree path plus is an odd cycle of length three. A separate isolated vertex receives either color and does not remove the obstruction.
Worked example 1.2.5
(A five-cycle: the conflict lies away from the root)
Take the cycle and root the search at . Then have depth and have depth , with parents and respectively. The edge joins two vertices of depth , so it is the conflict. Their lowest common ancestor is , and the tree path has length : it is . Adding gives the whole five-cycle as the witness. Here the witness passes through the root, as in the triangle; in general the lowest common ancestor can lie deeper, and only the parts of the two root paths below it are used.
Counterexample mode
Checking one component is not enough
A graph may have a bipartite component and a separate triangle. A search starting only in the first component finds no conflict, but the full graph is not bipartite. Restarting from each uncolored component is part of the algorithm, not a cosmetic detail.
Common mistake
(One even cycle certifies nothing)
Exhibiting an even cycle does not show that a graph is bipartite. contains the four-cycle , yet is a triangle. The criterion requires the absence of every odd cycle, which in practice is certified by a proper two-coloring of the whole graph.
Common mistake
(A conflict from free choices is not a witness)
Coloring vertices one at a time with arbitrary choices can produce a clash in a bipartite graph. On the path , choose and before anything links them; then is forced, and must differ from both and , which is impossible. Yet the path is bipartite. A conflict certifies an odd cycle only when every color involved was forced from one root of the same component, as in breadth-first search.
Exercises
Quick check
(Give a two-coloring of the six-cycle .)
Solution · Answer
Use and .
Quick check
(Explain why adding a chord between two vertices of the same color in a bipartite graph destroys that particular coloring. Must every new edge destroy bipartiteness?)
Solution · Answer
The new edge has equal-colored endpoints, violating that coloring. No: an edge between opposite sides can preserve it, for example a missing cross-edge in a bipartite graph.
Quick check
(A breadth-first tree has root with children and the graph also contains . Give the odd-cycle witness.)
Solution · Answer
The tree path plus is a three-edge cycle.
Quick check
(What output should the algorithm give for three isolated vertices?)
Solution · Answer
Any partition of the three vertices is a proper two-coloring. Restarting at each vertex may put all three in one class and leave the other empty.