In everyday language, “largest-looking” and “cannot add another edge” sound like the same claim. In graph matching, they are not, and that wording difference can change the answer. On one fixed bipartite graph, maximal, maximum and perfect matchings differ, and an augmenting path can turn a locally stuck choice into an optimal one. This idea belongs in the wider GATE CS Exam Preparation route.
Matching vocabulary: edges cannot share an endpoint
In an undirected graph G=(V,E), a matching M is a subset of edges in which no two selected edges share a vertex. The size |M| counts selected edges, not the vertices they cover. An endpoint of a selected edge is matched, or saturated. Every other vertex is exposed, or free.
Take the path P4 with vertices u1-u2-u3-u4. The set {u1u2,u3u4} is a matching of size 2 and saturates all four vertices. The set {u1u2,u2u3} is not a matching because both edges use u2. The set {u2u3} is valid, has size 1, and leaves u1 and u4 exposed.
The matching number ν(G) is the maximum matching size. The Graph Theory: Euler, Hamiltonian, Coloring for GATE CS guide places it beside paths, cycles and colouring. The matching problem is disjoint-edge selection.
Maximal, maximum and perfect answer different questions
Use three separate tests:
A matching is maximal if no unused edge can be added while preserving the matching property.
A matching is maximum if no matching anywhere in the graph has more edges.
A matching is perfect if every vertex is saturated.
Every perfect matching is maximum because it has |V|/2 edges, the largest possible number of pairwise endpoint-disjoint edges. Every maximum matching is maximal because an addable edge would produce a larger matching. Neither converse is true.
In P5=v1-v2-v3-v4-v5, {v1v2,v3v4} is maximum with size 2, but it cannot be perfect because one of the five vertices remains exposed. Also, perfect does not mean unique. In the cycle C4, both {v1v2,v3v4} and {v2v3,v4v1} are perfect matchings. The fixed graph below supplies the other important counterexample: a maximal matching that is not maximum.
Worked example: a greedy maximal matching gets stuck
Fix the bipartite graph with left side L={A,B,C,D}, right side R={1,2,3,4}, and edge set
E={A1,A2,B2,C2,C3,D3,D4}.
The greedy order is A2, then D3:
Select
A2.Select
D3, which shares no endpoint withA2.The result is
M0={A2,D3}, so|M0|=2.
Vertices A,D,2,3 are saturated, while B,C,1,4 are exposed. Test every remaining edge. A1 meets saturated A. Both B2 and C2 meet saturated 2. Edge C3 meets saturated 3, and D4 meets saturated D. No single edge can be added, so M0 is maximal.
But it is not maximum. Consider
M*={A1,B2,C3,D4}.
Its four edges have pairwise distinct endpoints, so |M*|=4: the left endpoints are A,B,C,D, and the right endpoints are 1,2,3,4, with no repetition. Any matching in this graph has at most four edges because each selected edge uses a different vertex from the four-vertex left side. Therefore 4 is both an upper bound and an achieved size: ν(G)=4. The matching M* saturates all eight vertices, making it maximum and perfect.
Augmenting paths repair the local choice
Relative to a matching M, an alternating path uses edges alternately outside and inside M. An augmenting path begins and ends at exposed vertices. It therefore has one more unmatched edge than matched edge. Flipping membership along the path adds the unmatched edges, removes the matched edges, and increases the matching size by exactly 1.
Start from M0={A2,D3}. The path 1-A-2-B is augmenting: A1 is unmatched, A2 is matched, and B2 is unmatched. Flip those three edges. Remove A2, add A1 and B2, and retain D3. This gives M1={A1,B2,D3}, with size 2-1+2=3.
From M1, use C-3-D-4. Here C3 is unmatched, D3 is matched, and D4 is unmatched. Removing D3 and adding C3,D4 gives M2={A1,B2,C3,D4}, with size 3-1+2=4.
Berge's criterion says that a matching is maximum if and only if no augmenting path exists. Maximality is only a one-edge addition check. Maximum matching needs this global certificate.
When can a perfect matching exist? Parity and Hall's condition
A perfect matching needs an even number of vertices, but that is not enough. The star K1,3 has four vertices, yet its maximum matching has size 1 because every edge uses the centre.
For a bipartite graph, Hall's theorem tests whether a matching can saturate the left side L. It exists if and only if |N(S)| >= |S| for every subset S of L, where N(S) is the set of right-side neighbours of S. If the sides have equal size, a matching that saturates L is perfect.
Consider L={p,q,r}, R={x,y,z}, and E={px,qx,ry,rz}. Choose S={p,q}. Then N(S)={x}, so |N(S)|=1<2=|S|. Hall's condition fails, and no matching can saturate L, even though each side has three vertices. The maximum size is 2, achieved for example by {px,ry}. For a structured route through related discrete-mathematics ideas, use Engineering Mathematics for GATE Exam.
Traps that make a plausible answer wrong
Reading maximal as largest. First apply the add-one-edge test to
M0. Then compare its size 2 withν(G)=4. It is maximal, not maximum.Assuming greedy means maximum. The order
A2,D3gets stuck, whileA1,B2,C3,D4covers every vertex in the same graph. Search for an augmenting path instead.Checking only even order. The graph
K1,3has four vertices but no perfect matching. In a bipartite graph, test Hall's condition or construct the matching.Counting saturated vertices as matching size. The matching
M*saturates 8 vertices but contains 4 edges, so|M*|=4.Saying “the” perfect matching. The cycle
C4has two distinct perfect matchings. A maximum matching can also leave a vertex exposed, as the size-2 maximum matching inP5does.
How exams test these distinctions
Expect short tasks built from the same checks:
Classify
M0={A2,D3}as maximal but not maximum.Calculate
ν(G)=4by giving a size-4 matching and the four-vertex-side upper bound.Flip
1-A-2-Bto changeM0intoM1={A1,B2,D3}.Reject a perfect matching in the Hall obstruction because
|N({p,q})|=1<2.
For true or false, “Every maximum matching is maximal” is true. “Every maximal matching is maximum” is false, and M0 is the exact counterexample. Name the implication or exhibit the counterexample instead of trusting intuition.
For adjacent practice on Euler routes, graph colouring and trees, work through Graph Theory MCQs: 12 Solved Euler, Coloring, Trees.
Short version and the next step
Verify that selected edges have disjoint endpoints.
Test whether one edge can be added before calling a matching maximal.
Search for an augmenting path before calling it maximum.
Check whether every vertex is saturated before calling it perfect.
In our graph, M0 is maximal at size 2, while two augmentations reach the perfect maximum M2 at size 4. Continue with GATE Guidance by Sanchit Sir for the broader CS preparation route.
