Bipartite matching: Hall's condition and vertex covers
Objectives and prerequisites
Apply Hall's theorem to a specified side, find an augmenting path in a bipartite graph, and certify a maximum matching with an equal-sized vertex cover. Prerequisites: matching, alternating/augmenting paths and finite sets. Graphs are finite, simple and undirected, with a stated bipartition L,R; every edge joins L to R. Matching size always means number of edges.
This lesson develops structural correctness and small hand-worked searches. It does not claim that listing all subsets is an efficient large-graph algorithm, or that the bipartite search directly implements a general-graph blossom algorithm.
1. Covering one side is not necessarily perfect
A matching covers L if every vertex of L is matched to a distinct neighbor in R. This requires |L|≤|R|, but unequal side sizes do not prevent covering the smaller side. A perfect matching covers both sides, so it requires |L|=|R| in a bipartite graph.
The equal-size requirement alone is not sufficient. Let L={a,b,c}, R={1,2,3}, with edges {a1,b1,c2,c3}. Both sides have size 3 and every vertex has a neighbor. Still a and b both require vertex 1, so they cannot both be matched. A matching of size 2 exists, such as {a1,c2}, and no size-3 matching exists.
This is a collective obstruction: checking each vertex separately misses the competition within a subset. We need to count the distinct available neighbors of a whole set, not add degrees and double-count shared neighbors.
2. Hall's theorem and why its condition is necessary
For S⊆L, define N(S)={r∈R: some s∈S is adjacent to r}. The neighborhood is a set, so a neighbor reached by several edges is counted once.
Hall's theorem: a matching covering L exists if and only if |N(S)|≥|S| for every S⊆L. The empty subset satisfies 0≥0 automatically. To disprove the existence of an L-covering matching, one subset with too few neighbors suffices. To prove it by Hall, all subsets must satisfy the condition, either by enumeration for a tiny graph or by one general argument.
Necessity follows from any proposed matching: vertices in S need distinct matched neighbors, all inside N(S), so at least |S| neighbors must be available. In the graph above, S={a,b} has N(S)={1}; 1<2 is a certificate of impossibility. Notice N(L)={1,2,3} has size 3, so checking only the whole left side would incorrectly pass this graph.
The sufficiency direction is what makes Hall's theorem powerful: absence of every such obstruction guarantees a matching, not merely the absence of an obvious local problem.
3. Worked positive example with unequal sides
Take L={a,b,c}, R={1,2,3,4}, and edges {a1,a2,b2,b3,c1,c3,c4}. The neighborhoods of singletons have sizes 2,2,3. For pairs, N({a,b})={1,2,3}, N({a,c})={1,2,3,4}, and N({b,c})={1,2,3,4}. Finally N(L)=R has size 4.
Every nonempty subset meets Hall's bound; the empty one does too. A concrete matching is {a2,b3,c4}, covering L with 3 edges. Since |L|=3, no matching can be larger. It is maximum but not perfect: right vertex 1 remains unmatched. Hall's conclusion must name the covered side; do not silently strengthen it to perfectness.
One useful theorem follows by counting edges. In a finite d-regular bipartite graph with d≥1, d|L|=d|R|, so the side sizes are equal. For any S⊆L, exactly d|S| edges leave S, and at most d|N(S)| can enter N(S). Therefore |S|≤|N(S)| and Hall gives a perfect matching. The requirement d≥1 matters: an edgeless graph with isolated vertices is 0-regular but has no perfect matching when vertices are present.
4. Search for alternating paths with directions
Given a matching M, start from every unmatched left vertex. During a search, follow edges outside M from left to right, and edges inside M from right to left. Reaching an unmatched right vertex supplies an augmenting path. The search directions enforce alternation; ordinary reachability with no matching information is not enough.
Example: L={a,b,c},R={1,2,3}, edges {a1,a2,b1,c2,c3}, and M={a1,c2}. The unmatched left vertex is b and unmatched right vertex is 3. Follow b→1 (outside M), 1→a (inside), a→2 (outside), 2→c (inside), c→3 (outside). Flipping this path gives {b1,a2,c3}, a perfect matching of size 3.
The failed strategy “give b a currently free direct neighbor” would stop, because b's only neighbor 1 is occupied. The alternating path rearranges earlier assignments and frees the needed capacity without leaving old vertices unmatched.
Each augmentation raises size by exactly 1, so only finitely many are possible. If a search from all unmatched left vertices reaches no unmatched right vertex, there is no augmenting path and the matching is maximum. A traversal can inspect each vertex and edge a bounded number of times per search, but this lesson's proof does not depend on memorizing a complexity formula.
5. Vertex covers provide an upper bound
A vertex cover C⊆V touches every edge: for each uv∈E, at least one of u or v belongs to C. A minimum vertex cover has the smallest possible number of vertices. This differs from a matching, which selects edges, and from an edge cover, which selects edges to touch vertices.
Every matching has size at most every vertex cover's size. The reason is simple: each matching edge needs a cover vertex, and distinct matching edges have disjoint endpoints, so they require distinct cover vertices. Thus a matching with k edges and a vertex cover with k vertices certify each other as optimal, even before invoking a named theorem.
In the obstruction graph {a1,b1,c2,c3}, M={a1,c2} has size 2. The vertex set {1,c} touches all four edges, so a size-2 cover exists. The matching-cover inequality now proves ν=2 and minimum cover size τ=2. A size-1 cover is impossible because no one vertex can touch both disjoint matching edges.
Kőnig's theorem states that ν(G)=τ(G) for every finite bipartite graph. It does not say that the sets themselves are equal: one contains edges, the other vertices. It also does not hold for every nonbipartite graph. A triangle has maximum matching size 1 but minimum vertex cover size 2.
6. Construct a minimum cover from a maximum matching
Let M be maximum. Carry out the directed alternating search from all unmatched left vertices. Let Z_L and Z_R be the reached vertices in L and R. Then
C=(L\Z_L) ∪ Z_R
is a minimum vertex cover.
Why does it cover every edge? Suppose an edge lr had l∈Z_L and r∉Z_R, so neither endpoint would be selected. If lr is outside M, the search from l would reach r, a contradiction. If it is inside M, a reached matched left vertex was reached through its matching edge from r; unmatched starting vertices have no such edge. Again r would be reached. Thus no edge is left uncovered.
Why does C have |M| vertices? No unmatched right vertex is reached, or there would be an augmenting path. Every unmatched left vertex is a starting vertex and is excluded from C. For each matched edge, either both endpoints are reached or neither is; in the first case C selects its right endpoint, in the second its left endpoint. Hence exactly one selected vertex corresponds to each matching edge. This gives |C|=|M| and proves optimality.
For the obstruction graph with M={a1,c2}, the only unmatched left vertex is b. The search reaches b,1,a and no others. Thus Z_L={a,b},Z_R={1}, and C={c,1}, matching the direct certificate above.
Checklist and scope
State L and R. Count N(S) as distinct neighbors, not edges. Separate Hall's all-subsets requirement from a single-subset counterexample. Keep side-covering separate from perfect matching. For a hand search, alternate outside/inside edges in the correct direction. For optimality, exhibit a matching and a matching-sized vertex cover, or establish no augmenting path. Weighted assignments, stable matching and arbitrary-graph vertex-cover algorithms are different problems and are not completed here.
Original practice: six single-correct MCQs
Original questions, not previous-year questions. Choose exactly one option. Graphs are finite, simple and undirected; preserve each stated matching, labeling and coloring convention.
C01. Let L={a,b,c}, R={1,2,3}, and E={a1,b1,c2,c3}. Which set explicitly violates Hall’s condition for saturating L?
A. S={c}, since |N(S)|=2 B. S=L, since |N(S)|=3 C. S={a,b}, since |N(S)|=1 D. S=∅, since |N(S)|=0
Answer: C
A: Here 2≥1, so the condition holds for this subset.
B: Here 3≥3; testing only the full left side misses the obstruction.
C: Two left vertices compete for the same sole neighbor 1: |N(S)|=1<2=|S|.
D: The empty subset satisfies 0≥0; it is never a violating witness.
C02. For E={a1,b1,c2,c3} on the same two three-vertex parts, what are maximum matching size ν and minimum vertex-cover size τ?
A. ν=2, τ=2 B. ν=3, τ=3 C. ν=1, τ=2 D. ν=2, τ=3
Answer: A
A: Matching {a1,c2} has size 2, and cover {1,c} meets every edge. Since ν≤τ, these equal certificates prove both optima.
B: Hall’s violating subset prevents a three-edge matching, and the displayed two-vertex cover disproves τ=3.
C: The disjoint edges a1 and c2 already give a matching of size 2.
D: Cover {1,c} has size 2, so a minimum cover cannot require 3.
C03. A bipartite graph has |L|=3, |R|=4 and a matching saturating all of L. What follows?
A. The matching is perfect in the whole graph. B. The matching has four edges. C. A larger matching must exist because one vertex is exposed. D. The matching is maximum of size 3 but not perfect in the whole graph.
Answer: D
A: One right-side vertex remains exposed because the parts have unequal sizes.
B: Every matching edge uses a distinct left vertex; only three are available.
C: An exposed vertex alone is insufficient: every matching edge needs a distinct left endpoint.
D: Saturating three left vertices uses three edges, meeting the smaller-part upper bound. Exactly one of the four right vertices remains unmatched.
C04. Which statement about finite d-regular bipartite graphs is valid under the stated d≥1 assumption?
A. They always have more left vertices than right vertices. B. They have equal-sized parts and a perfect matching. C. They have no perfect matching when d is odd. D. The conclusion holds for every d=0 graph with arbitrary part sizes.
Answer: B
A: Counting edges gives d|L|=d|R|, and d>0 permits cancellation to equal sizes.
B: For S⊆L, its d|S| incident edges enter N(S), whose total capacity is at most d|N(S)|. Hall holds, and equal part sizes make the saturation perfect.
C: The proof works for every positive d. Degree 1 graphs are already disjoint matching edges.
D: With d=0, isolated vertices need not admit a perfect matching, and the parts need not have equal size. Division by d would be invalid.
C05. For E={a1,a2,b1,c2,c3} and M={a1,c2}, flip the augmenting path b−1−a−2−c−3. Which matching results?
A. {a1,c2,b1} B. {a1,c2,c3} C. {b1,a2,c3} D. {a2,c2}
Answer: C
A: a1 and b1 share vertex 1; simply adding the first edge does not produce a matching.
B: c2 and c3 share c; the old matching edges on the path must be removed.
C: Remove a1,c2 and add b1,a2,c3. All six vertices are covered once, and size rises from 2 to 3.
D: Both a2 and c2 use right vertex 2, so this is not a matching.
C06. Which example shows why the equality ν=τ cannot be claimed for every simple graph?
A. A triangle has ν=1 and τ=2. B. A single edge has ν=τ=1. C. An edgeless graph has ν=τ=0. D. A four-vertex path has ν=τ=2.
Answer: A
A: Any two triangle edges intersect, so ν=1. One vertex misses the opposite edge, but two cover all edges, so τ=2. The graph is not bipartite.
B: This bipartite example satisfies equality and is not a counterexample.
C: Both quantities are zero, so equality holds rather than fails.
D: A two-edge matching and a two-vertex cover certify equality on this bipartite path.
Sources and scope
This original lesson develops the matching/colouring portion of Discrete Mathematics in Section 1 of the official GATE 2027 CS syllabus. The syllabus establishes relevance, not a promise of full-subject mastery. The MIT references support graph definitions and theorems; examples, exposition and practice here are original. Further depth is identified in the lesson rather than assumed complete.
Sources opened and checked 2026-10-14.
Sign in to keep your progress. Sign in