Bipartite: V = A∪B with edges only between A and B. Equivalent: χ(G)=2, no odd cycles. Testable in O(n+m) via BFS 2-coloring. König: ν=τ. Hall: perfect matching iff |N(S)|≥|S|. Many NP-hard problems are polynomial on bipartite.
How to Use
Select graph:
- Bipartite? Yes/No
- Partition: A, B sets
- Odd cycle: If not bipartite
König's Theorems
For bipartite: (1) max matching = min vertex cover (ν=τ). (2) max independent set = min edge cover. (3) Edge coloring: χ'=Δ. These fail for general graphs but hold perfectly for bipartite.
BFS 2-Coloring
Start BFS, alternate colors 0/1 between levels. If any edge connects same-color vertices → odd cycle → not bipartite. O(n+m) time. Works on disconnected graphs by running BFS from each component.
Step-by-Step Instructions
- 1Select graph.
- 2Run BFS coloring.
- 3Check edges.
- 4Find partition.
- 5Apply König.