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.
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
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 it
- 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.
Next recommended lesson
Continue through this topic with Least You Need to Know: Euler Trails and Cycles.
Least You Need to Know: Euler Trails and CyclesRelated lessons
Keep going with nearby lessons in the same topic.