Bipartite Matching

Graph Theory · Axiom Academy

Matchings in bipartite graphs, maximum matchings, and their profound connection to vertex covers A matching is a set of edges in a graph where no two edges share a common vertex. Think of it as a way to pair up vertices without conflicts. A matching M in a graph G = (V, E) is a subset M ⊆ E such that no two edges in M share a vertex. If a vertex v is an endpoint of some edge in M, we say v is matched or saturated . Otherwise, v is unmatched or free . In a bipartite graph with vertices A, B, C on the left and 1, 2, 3 on the right, if we have edges A-1, B-2, and C-3, selecting all three edges forms a perfect matching since every vertex is matched exactly once. 2. Why Bipartite Graphs are Special for Matchings Bipartite graphs have a unique structure that makes matching problems tractable. Unlike general graphs, we can find maximum matchings efficiently in bipartite graphs. No odd cycles: This is crucial for matching algorithms Augmenting paths: Easy to identify paths that increase matching size Polynomial-time solvable: Maximum matching can be found efficiently Perfect characterization: Hall's theorem gives exact conditions for perfect matchings 3. Augmenting Paths: The Key to Maximum Matchings An augmenting path is a path that starts and ends at unmatched vertices, alternating between edges not in the matching and edges in the matching. Given a matching M, an M-augmenting path P is a path where: P starts at an unmatched vertex in one partition

This is the written version of the interactive lesson above. See the full Graph Theory course.