Bipartite graphs and matchings (intro)

SECTION 1

Historical Context & Motivation

The study of bipartite graphs and matchings sits at one of the most productive intersections of pure combinatorics and applied optimization. The underlying question is deceptively simple: given two distinct groups of objects and a set of allowable pairings between them, how can we optimally assign elements from one group to the other? This question arises naturally in scheduling, resource allocation, network routing, and even organ-donor matching programs. The mathematical theory that answers it has roots stretching back over a century, and its development intertwines the contributions of several eminent mathematicians working across combinatorics, linear programming, and algorithm design.

1736

Euler and the Königsberg Bridges

Leonhard Euler's solution to the Königsberg bridge problem established the foundations of graph theory. While the original problem concerned traversability, Euler's framework of vertices and edges became the language in which bipartiteness would later be formalized.

1916

König's Theorem

Dénes König proved that in bipartite graphs the size of a maximum matching equals the size of a minimum vertex cover. This duality result, now known as König's theorem, became a cornerstone of combinatorial optimization and revealed deep structural properties unique to bipartite graphs.

1935

Hall's Marriage Theorem

Philip Hall published a necessary and sufficient condition for a perfect matching in a bipartite graph, framed as a marriage problem: every subset of one side must have enough collective neighbors on the other side. Hall's condition remains central to matching theory.

1955

The Hungarian Algorithm

Harold Kuhn introduced an efficient algorithm for weighted bipartite matching, drawing on work by König and Egerváry. The Hungarian algorithm provided a polynomial-time solution to the assignment problem and demonstrated that theoretical elegance could translate directly into computational efficiency.

1973

Hopcroft–Karp Algorithm

John Hopcroft and Richard Karp devised an algorithm that finds a maximum matching in O(√V · E) time by using shortest augmenting paths in phases. This result set the standard for efficient unweighted bipartite matching and influenced decades of subsequent algorithm design.

The central question this lesson addresses is twofold. First, when can a graph be cleanly separated into two independent sides—and how do we verify this? Second, once we have a bipartite graph, how do we find the largest collection of edges that pair elements without conflicts? Understanding these questions equips you with tools that reappear throughout combinatorics, algorithm design, and operations research.

SECTION 2

Core Principles & Definitions

Before diving into algorithms and theorems, it is essential to establish the foundational definitions rigorously. A bipartite graph is an undirected graph G = (V, E) whose vertex set V can be partitioned into two disjoint, independent sets U and W such that every edge in E connects a vertex in U to a vertex in W. Equivalently, G is bipartite if and only if it contains no odd-length cycle—a characterization that provides both a structural insight and a practical test. A matching M in a graph G is a subset of edges such that no two edges in M share a common endpoint; informally, every vertex is "used" at most once. A maximum matching is a matching of greatest possible cardinality, and a perfect matching is one that saturates every vertex of the graph.

Bipartiteness

A graph is bipartite if and only if it is 2-colorable: you can assign every vertex one of two colors so that no edge joins two vertices of the same color. This is equivalent to the absence of odd cycles.

Matching

A set of edges M ⊆ E where every vertex appears in at most one edge of M. The cardinality |M| is called the size of the matching.

Augmenting Path

A path in G that alternates between edges not in M and edges in M, starting and ending at unmatched (free) vertices. By Berge's theorem, a matching is maximum if and only if no augmenting path exists.

Vertex Cover

A set S ⊆ V such that every edge has at least one endpoint in S. By König's theorem, in bipartite graphs the minimum vertex cover equals the maximum matching in size.

Hall's Condition

A bipartite graph G = (U ∪ W, E) has a matching saturating every vertex of U if and only if for every subset S ⊆ U, |N(S)| ≥ |S|, where N(S) denotes the neighborhood of S in W.

✦ KEY TAKEAWAY

Think of a bipartite graph as a job fair where one side of the room holds job applicants and the other side holds employers. Edges represent which applicants are qualified for which positions. A matching assigns applicants to positions with no conflicts—each person gets at most one job and each position is filled by at most one person. A maximum matching fills as many positions as possible, and a perfect matching means everyone walks out employed and every position is filled.

SECTION 3

Visualizing Bipartite Graphs

The canonical way to draw a bipartite graph places the two vertex sets U and W in separate columns (or rows), with edges crossing between them. This visual layout immediately reveals the bipartite structure and makes matchings easy to identify. In the diagram below, vertices on the left belong to set U and vertices on the right belong to set W. Thin gray edges represent the full edge set E, while the thick highlighted edges show a maximum matching of size 3. Notice that vertex u₄ remains unmatched because no augmenting path can reach it without disturbing the existing matching.

A bipartite graph G = (U ∪ W, E) with |U| = 4 and |W| = 4. The cyan edges form a maximum matching M of size 3. Vertex u₄ and w₄ are free (unmatched). The dashed borders on u₄ and w₄ indicate their unmatched status.

Observe that although the graph has four vertices on each side, the maximum matching has size 3, not 4. There is no perfect matching here because u₄ connects only to w₃ and w₄, and w₃ is already claimed by u₃. Attempting to match u₄ to w₃ would free u₃, but u₃'s only other neighbor is w₂, which is matched to u₂—following this chain does not yield a free vertex, so no augmenting path exists and the matching is maximum. This reasoning previews the augmenting path technique that we will formalize in the mathematical framework section.

SECTION 4

Mathematical Framework

The theoretical backbone of bipartite matching rests on three pillars: Berge's characterization of maximum matchings via augmenting paths, Hall's necessary-and-sufficient condition for a perfect matching (or, more precisely, a matching saturating one side), and König's min-max duality between maximum matchings and minimum vertex covers. Together these results form a remarkably coherent framework in which structural, existential, and algorithmic questions all receive elegant answers.

Berge's Theorem (1957)

BERGE'S THEOREM

M is a maximum matching ⟺ there is no M-augmenting path in G

An M-augmenting path is a path P = v₀ e₁ v₁ e₂ … eₖ vₖ where v₀ and vₖ are free (not in V(M)), and the edges alternate between E \ M and M. Symmetric differencing M ⊕ P increases |M| by 1.

Hall's Marriage Theorem (1935)

HALL'S CONDITION

∃ matching saturating U ⟺ ∀ S ⊆ U : |N(S)| ≥ |S|

Here G = (U ∪ W, E) is bipartite and N(S) = { w ∈ W : ∃ u ∈ S with uw ∈ E }. The condition states that no subset of U is "bottlenecked" by having too few collective neighbors. When |U| = |W| and Hall's condition holds, the matching is perfect.

König's Theorem (1931)

KÖNIG'S MIN-MAX DUALITY

ν(G) = τ(G) for every bipartite graph G

ν(G) denotes the size of a maximum matching and τ(G) the size of a minimum vertex cover. This equality fails for general graphs (consider the triangle K₃, where ν = 1 but τ = 2), making it a distinctively bipartite phenomenon. The theorem is equivalent to LP duality applied to the incidence matrix of a bipartite graph, which is always totally unimodular.

💡 Why Bipartite is Special

König's theorem relies on the total unimodularity of bipartite incidence matrices—a property that guarantees LP relaxations have integer optima. This is why maximum matching in bipartite graphs can be solved as a linear program without integrality constraints, whereas general matching requires the more sophisticated Edmonds blossom algorithm to handle odd cycles.

SECTION 5

Testing Bipartiteness & Structural Properties

Before searching for matchings, one must verify that a graph is bipartite. The fundamental characterization—a graph is bipartite if and only if it contains no odd-length cycle—yields a practical linear-time algorithm. Perform a BFS/DFS 2-coloring: start at any vertex, color it 0, and assign the opposite color to every neighbor. If at any point a neighbor already has the same color as the current vertex, an odd cycle has been detected and the graph is not bipartite. This procedure runs in O(|V| + |E|) time and also produces the bipartition (U, W) when it succeeds.

Left: a graph with only even cycles (C₄) admits a valid 2-coloring (violet = 0, amber = 1), confirming bipartiteness. Right: the triangle C₃ forces a conflict at the bottom vertex, which must be both color 0 and color 1, proving the graph is not bipartite.

Several important structural facts follow from bipartiteness. First, every tree is bipartite because trees contain no cycles at all. Second, every even cycle C₂ₖ is bipartite. Third, the complete bipartite graph K_m,n has every possible edge between sets of sizes m and n, so |E| = m × n. This graph always has a matching of size min(m, n), saturating the smaller side. Fourth, bipartite graphs are closed under subgraph inclusion—any subgraph of a bipartite graph is itself bipartite, since removing edges or vertices cannot create odd cycles.

Bipartiteness of common graph families

Graph Family	Bipartite?	Reason
Path Pₙ	Always	A path is a tree; trees have no cycles.
Cycle Cₙ	Iff n is even	Odd cycles are the obstruction to bipartiteness.
Complete graph Kₙ (n ≥ 3)	Never	K₃ is a subgraph and is an odd cycle.
Hypercube Qₙ	Always	Partition by parity of the number of 1-bits in the binary label.
Petersen graph	Never	Contains 5-cycles (odd length).

SECTION 6

Worked Example: Finding a Maximum Matching

Consider a bipartite graph G = (U ∪ W, E) where U = {a, b, c, d} and W = {1, 2, 3, 4} with edges E = {a1, a2, b1, b3, c2, c3, d3, d4}. We wish to find a maximum matching using the augmenting path method.

Maximum Matching via Augmenting Paths

Step 1 — Initialize with a greedy matchingScan the vertices of U in order and greedily match each to any available neighbor. Match a → 1 (first available neighbor of a), then b → 3 (since b's neighbor 1 is already taken), then c → 2 (c's neighbor 2 is free). Now d's neighbors are 3 and 4; vertex 3 is taken by b, but 4 is free, so match d → 4.

Greedy matching M₀ = {a1, b3, c2, d4}, |M₀| = 4.

Step 2 — Check for free verticesA free vertex is one not covered by the current matching. Inspect U: a, b, c, d are all matched. Inspect W: 1, 2, 3, 4 are all matched. Since there are no free vertices, no augmenting path can exist.

No free vertices found.

Step 3 — Apply Berge's theoremBerge's theorem states that a matching is maximum if and only if no augmenting path exists. Since every vertex in both U and W is matched, no augmenting path can even start (augmenting paths must begin and end at free vertices). Therefore M₀ is a maximum matching.

M₀ = {a1, b3, c2, d4} is a maximum (and perfect) matching of size 4.

Step 4 — Verify Hall's conditionSince a perfect matching exists, Hall's condition must hold for every subset S ⊆ U. Let's verify a critical case: S = {b, c, d}. The neighborhood N(S) = N({b, c, d}) = {1, 2, 3, 4} (b → {1,3}, c → {2,3}, d → {3,4}), so |N(S)| = 4 ≥ 3 = |S|. Checking all 2⁴ = 16 subsets of U would confirm that |N(S)| ≥ |S| in every case, consistent with the existence of a perfect matching.

Hall's condition verified: ∀ S ⊆ U, |N(S)| ≥ |S|.

Step 5 — König's theorem corollaryBy König's theorem, the minimum vertex cover also has size 4. Since τ(G) = 4 = |V|/2 and the matching is perfect, one valid minimum vertex cover is the entire set U (or the entire set W). However, smaller covers may exist for non-perfect matchings—this is where König's theorem becomes truly powerful in optimization.

Minimum vertex cover has size τ(G) = ν(G) = 4.

🔍 What if the greedy matching fails?

Suppose the greedy step had produced M' = {a1, b3, c2} and left d unmatched (perhaps we processed in a different order or edges differed). We would then search for an augmenting path starting at d. If d is adjacent to 3, which is matched to b, we follow the alternating path d → 3 → b → 1 → a. But a has no other free neighbor, so this path dead-ends. We try d → 4, which is free, giving the augmenting path d → 4 of length 1. Augmenting along this path adds d4 to the matching, yielding size 4. The process of systematically seeking and augmenting along such paths is the essence of the Hungarian method.

SECTION 7

Bipartite vs. General Matching

Bipartite matching is a special case of general graph matching, but this specialization buys us significant theoretical and computational advantages. The absence of odd cycles is not merely a structural curiosity—it fundamentally simplifies the matching problem. In general graphs, odd cycles create "blossoms" that complicate augmenting-path searches and require Edmonds' blossom-shrinking technique (1965) to resolve. In bipartite graphs, augmenting-path searches via BFS are straightforward and never encounter this complication. The following table summarizes the key contrasts.

Bipartite vs. general graph matching

Property	Bipartite Graphs	General Graphs
König's theorem (ν = τ)	Holds	Fails (e.g., K₃: ν = 1, τ = 2)
LP relaxation integrality	Always integral (total unimodularity)	Half-integral; needs Edmonds polytope
Augmenting path search	Simple BFS/DFS alternating	Requires blossom shrinking
Best known time complexity	O(√V × E) — Hopcroft–Karp	O(√V × E) — Micali–Vazirani
Weighted version	O(V³) — Hungarian algorithm	O(V³) — Edmonds with weights
Hall-type existence condition	Hall's marriage theorem	Tutte–Berge formula (more complex)

✦ KEY TAKEAWAY

The bipartite constraint is analogous to the difference between solving a system of equations where the coefficient matrix is totally unimodular versus one where it is not. In the TU case, linear relaxations automatically produce integer solutions—no rounding heuristics or branch-and-bound needed. Similarly, bipartite matching avoids the combinatorial headaches that odd cycles inflict on general matching algorithms, making the theory cleaner and the algorithms faster in practice despite matching asymptotic bounds.

SECTION 8

Connections to Advanced Theory

The introductory results on bipartite matchings open the door to a rich landscape of advanced topics. In combinatorial optimization, network flow provides a unifying framework: a bipartite matching problem can be modeled as a maximum flow problem on a network with a source connected to every vertex in U, a sink connected to every vertex in W, and unit-capacity edges for every edge in E. The max-flow min-cut theorem then yields König's theorem as a special case. In algebraic combinatorics, the permanent of a 0-1 matrix counts the number of perfect matchings in a bipartite graph, connecting matching theory to linear algebra and complexity theory (computing the permanent is #P-complete by Valiant's theorem). In probabilistic combinatorics, random bipartite graphs give rise to sharp threshold phenomena for the existence of perfect matchings.

From introductory to advanced matching theory

Introductory Concept	Advanced Extension	Key Idea
Maximum matching	Maximum weight matching	Assign weights to edges; optimize total weight rather than cardinality.
Hall's condition	Deficiency version of Hall	When Hall's condition fails, the deficiency max(\|S\| − \|N(S)\|) over all S quantifies how far the graph is from admitting a saturating matching.
König's theorem	LP duality / total unimodularity	König's theorem is the combinatorial manifestation of strong duality for LPs with totally unimodular constraint matrices.
Augmenting paths	Network flow / Ford–Fulkerson	Augmenting paths in matchings are special cases of augmenting paths in flow networks.
Bipartite matching	General matching (Edmonds)	Handling odd cycles via blossom contraction extends the theory to arbitrary graphs.

As you advance, you will encounter the Gallai–Edmonds structure theorem, which generalizes the bipartite decomposition to arbitrary graphs, and stable matching (the Gale–Shapley algorithm), which adds preferences to the assignment problem. The 2012 Nobel Prize in Economics was awarded to Alvin Roth and Lloyd Shapley in part for their work on stable matchings and market design—a vivid reminder that the graph-theoretic ideas introduced in this lesson have profound real-world consequences.

SECTION 9

Practice Problems

PROBLEM 1 — CONCEPTUAL

Explain why the complete graph K₅ is not bipartite, but the complete bipartite graph K₂,₃ is. In your answer, reference the odd-cycle characterization and describe how the vertex sets are partitioned in K₂,₃.

PROBLEM 2 — BASIC CALCULATION

Let G be a bipartite graph with U = {a, b, c} and W = {x, y, z} and edges E = {ax, ay, bx, by, cy, cz}. Find a maximum matching and state its size. Does a perfect matching exist?

PROBLEM 3 — INTERMEDIATE

Consider the bipartite graph G with U = {a, b, c, d} and W = {1, 2, 3} with edges E = {a1, a2, b1, c2, c3, d3}. (a) Show that no perfect matching exists by finding a subset S ⊆ U that violates Hall's condition. (b) Find a maximum matching and verify its maximality using Berge's theorem.

PROBLEM 4 — APPLIED

A university needs to assign 5 teaching assistants (TAs) to 5 courses. Each TA is qualified for certain courses: TA₁ → {Math, CS}, TA₂ → {Math, Physics}, TA₃ → {CS, Biology}, TA₄ → {Physics, Chemistry}, TA₅ → {Biology, Chemistry}. Model this as a bipartite graph, determine whether a perfect assignment exists using Hall's condition, and find one if it does.

PROBLEM 5 — CRITICAL THINKING

Prove that every k-regular bipartite graph (k ≥ 1) has a perfect matching. (Hint: verify Hall's condition by counting edges incident to a subset S ⊆ U and its neighborhood N(S).)

SUMMARY

Lesson Summary

A bipartite graph is a graph whose vertex set can be partitioned into two independent sets, equivalently characterized as a graph with no odd-length cycles. Bipartiteness can be tested in linear time via BFS 2-coloring. A matching is a set of edges with no shared endpoints, and a maximum matching is one of greatest cardinality. Berge's theorem characterizes maximum matchings via the absence of augmenting paths, providing both a correctness certificate and an algorithmic strategy.

For bipartite graphs specifically, Hall's marriage theorem gives a necessary and sufficient condition (|N(S)| ≥ |S| for all subsets) for a matching that saturates one entire side, while König's theorem establishes the deep duality ν(G) = τ(G) between maximum matchings and minimum vertex covers—a property that fails in general graphs. These results connect naturally to network flow, linear programming duality, and the broader theory of combinatorial optimization, making bipartite matching one of the most foundational and far-reaching topics in discrete mathematics.