Graphs / Bipartite Graphs
Least You Need to Know: Bipartite Graphs
A graph is bipartite when its vertices can be split into two groups so every edge goes across the split. Odd cycles are the main obstruction.
The least you need to know
- A graph is bipartite exactly when it has no odd cycle.
- Two-coloring is a practical way to test bipartite structure.
- In a bipartite graph, edges never join vertices within the same part.
- Complete bipartite graphs have every possible cross-edge.
Key notation
U ∪ V
two vertex parts
K_{m,n}
complete bipartite graph
odd cycle
cycle of odd length
Tiny worked example
- A 4-cycle can be colored alternating red-blue-red-blue.
- Every edge joins different colors, so the graph is bipartite.
- A triangle cannot be colored this way, so it is not bipartite.
Common mistakes
- Students often think a graph is bipartite just because its vertices can be divided somehow.
- Students often miss that triangles are odd cycles.
- Students often confuse complete bipartite with complete graph.
How to recognize this kind of problem
- Try alternating two colors along a path.
- If you return to the start of an odd cycle, the colors clash.
- In `K_{m,n}`, degrees come from the opposite part.