← Back to the graphs page
Bipartite Graph
Nodes split into two groups with edges only across groups — never within. Equivalent to "2-colorable" and to "no odd-length cycle".
What to know
- Check bipartiteness by BFS/DFS coloring: alternate colors, any same-color edge fails it.
- Matching = pairing nodes across the two sides so no node is used twice.
- Maximum matching relates to minimum vertex cover via Kőnig’s theorem.
In the wild: Matching riders to drivers, students to schools, ads to slots, jobs to machines.
Algorithms to reach for
BFS/DFS two-coloring
O(V + E)Verify a graph is bipartite (LeetCode 785)
Hungarian algorithm
O(V³)Minimum-cost assignment of workers to jobs
Hopcroft-Karp
O(E · √V)Maximum bipartite matching fast
Practice problems — with full guides
Each problem has its own page: progressive hints, how to approach it, and the full solution.