Matchings and augmenting paths
Objectives and prerequisites
Distinguish maximal, maximum and perfect matchings; certify an exact matching size; improve a matching by an augmenting path; and separate cardinality from weight. Prerequisites: finite simple undirected graph terminology and paths. No graph has loops or parallel edges here. Edges ab and ba mean the same undirected edge. The size of a matching is its number of edges, not the number of covered vertices.
1. A matching selects edges without sharing endpoints
A matching M⊆E has no two edges incident to the same vertex. A vertex is matched or covered if it is an endpoint of an edge in M; otherwise it is unmatched or exposed. A matching with k edges covers exactly 2k vertices, so every matching on n vertices has size at most floor(n/2).
For a path 1−2−3−4, {12,34} is a matching, while {12,23} is not: both selected edges use vertex 2. A matching need not connect all vertices or form one connected subgraph. In fact, its selected edges are pairwise separate. Do not confuse a matching with a path, an edge cover or a vertex cover.
A maximal matching cannot be extended by simply adding another edge while retaining all its current edges. A maximum matching has the largest possible size among all matchings in the graph. Write ν(G) for that largest size. Maximum describes a global optimum; maximal describes the absence of one simple addition. Every maximum matching is maximal, but the converse can fail.
A perfect matching covers every vertex. It has n/2 edges, so n must be even. A perfect matching is maximum because it meets the floor(n/2) bound. A maximum matching need not be perfect, for example in a triangle where every matching has at most one edge.
2. Worked example: maximal but not maximum
Consider the six-vertex path with edges {12,23,34,45,56}. Let M={23,45}. Its unmatched vertices are 1 and 6. Every unused edge touches an already matched vertex, so no edge can simply be added; M is maximal.
However, M*={12,34,56} is a matching with 3 edges. The upper bound floor(6/2)=3 proves it is maximum, and it is perfect. Thus the earlier matching of size 2 was not maximum. Finding a larger matching may require removing some old edges, not only looking for an unused edge between two exposed vertices.
This example also shows how to prove an exact optimum: exhibit a matching of size 3 (lower bound ν≥3) and prove that no matching can exceed 3 (upper bound ν≤3). A displayed matching by itself gives only a lower bound.
3. Alternating and augmenting paths
Relative to a fixed matching M, an alternating path uses edges alternately outside and inside M. An augmenting path is an alternating simple path whose endpoints are both unmatched. It begins and ends with edges outside M, so it has one more outside edge than inside edge and an odd number of edges.
For M={23,45} in the six-vertex path, the path 1−2−3−4−5−6 is augmenting. Its edges alternate outside, inside, outside, inside, outside. Flip their membership: remove 23 and 45, and add 12,34,56. The matching grows from size 2 to size 3.
Why is the result still a matching? Each internal path vertex loses its old matching edge and gains one new matching edge. Each previously unmatched endpoint gains one. Vertices off the path keep their old status. The size rises by exactly 1 because an augmenting path contains k+1 outside edges and k inside edges.
An alternating path is not automatically augmenting. Its endpoints must be unmatched with respect to the current matching. An alternating cycle has equally many inside and outside edges; flipping it may give a different matching of the same size, not a larger one.
4. When no augmenting path exists
Berge's theorem says that a matching is maximum exactly when it has no augmenting path. One direction is immediate: an augmenting path produces a larger matching, so the current matching cannot be maximum.
For the other direction, compare M with a larger matching N. Consider only edges belonging to exactly one of them, their symmetric difference M△N. At any vertex there is at most one M-edge and at most one N-edge, so components of this subgraph are alternating paths, alternating cycles or isolated vertices.
Alternating cycles contain equal numbers of edges from each matching. If N has more edges overall, some path component must have one more N-edge than M-edge. That path begins and ends with N-edges, at vertices unmatched by M, so it is an augmenting path for M. Therefore a nonmaximum matching must have an augmenting path.
The theorem is a correctness criterion, not a claim that a naive path-search routine works equally easily in every graph. Odd cycles complicate efficient general-graph matching algorithms. The next lesson treats bipartite graphs, where alternating-path searches are simpler; blossom algorithms are beyond this sequence's current implementation scope.
5. Useful bounds and graph families
A maximal matching gives a factor-two size guarantee: if M is maximal and N is maximum, then |N|≤2|M|. Every edge of N must touch a vertex covered by M; otherwise that edge could be added to M. Since edges of N do not share endpoints, at most two of them can be accounted for by the two endpoints of any one M-edge. This proves the bound.
It can be tight. In the four-vertex path, the middle edge alone is maximal with size 1, while the two outer edges form a maximum matching of size 2. The guarantee concerns size, not optimality and not arbitrary edge weights.
For a path Pₙ or cycle Cₙ (n≥3 for the cycle), adjacent disjoint pairs give floor(n/2) edges and the vertex-count upper bound proves this is maximum. The complete graph Kₙ has the same matching number. A star K₁,ₖ with k≥1 has matching number 1 because every edge uses the centre.
Consequently an even number of vertices, connectedness and no isolated vertex together still do not guarantee a perfect matching: K₁,₃ has all three properties but maximum matching size 1 instead of 2. The issue is competition for the same centre, not a missing neighbor for an individual leaf.
6. Counting perfect matchings in a complete graph
In K₄ with labeled vertices, a perfect matching has two edges. Pair vertex 1 with one of the other 3 vertices; the remaining pair is then forced. There are 3 perfect matchings, not 6: the two edges are an unordered set, so exchanging their listing order does not create a new matching.
For K₆, choose the partner of the lowest-labeled remaining vertex: 5 choices, then 3, then 1. The count is 5·3·1=15. This rule uniquely determines each matching without ordering its edges. In general K₂ₖ has (2k−1)(2k−3)…1 perfect matchings, equivalently (2k)!/(2ᵏk!). The divisions remove each pair's internal ordering and the ordering among pairs. This formula concerns complete labeled graphs; missing edges invalidate it.
7. Cardinality and weight are different objectives
Suppose the four-vertex path has edge weights w(12)=1,w(23)=10,w(34)=1. The maximum-cardinality matching {12,34} has two edges and total weight 2. The matching {23} has one edge and total weight 10, so it wins the weight objective. An augmenting path raises cardinality, but need not raise weight.
Always state whether the task asks for maximum number of pairs, maximum total weight, or a maximum-cardinality matching with best weight among ties. These are different optimization problems. Our unweighted lessons and questions use cardinality unless weights are explicitly introduced.
Solving checklist
Check that selected edges exist and share no endpoints. Count covered vertices separately from edges. For maximality, ask whether any edge joins two exposed vertices. For maximum size, look for augmenting paths or an upper-bound certificate that matches the displayed matching. For perfectness, check every vertex. Never replace these different questions with the vague claim that a matching is “largest-looking.”
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. In the path 1−2−3−4−5−6, how should M={23,45} be classified?
A. Not a matching B. Maximal but not maximum C. Maximum and perfect D. Maximum but not perfect
Answer: B
A: The two selected edges have no common endpoint, so this is a matching.
B: Only vertices 1 and 6 are exposed, and they are not adjacent, so no edge can be added. Yet {12,34,56} is larger.
C: Vertices 1 and 6 are uncovered, and a matching of size 3 exists. Both claims fail.
D: Its size is 2 while the displayed three-edge matching attains the upper bound 3.
C02. An augmenting path contains three edges of the current matching. How many outside edges does it contain, and how much does flipping increase matching size?
A. 3 outside; increase 0 B. 4 outside; increase 4 C. 6 outside; increase 3 D. 4 outside; increase 1
Answer: D
A: An augmenting path begins and ends outside the matching, so outside edges outnumber inside edges by one.
B: Four edges are added but three old edges are removed; net gain is not four.
C: Alternation with both endpoints exposed gives four outside edges, not six.
D: The alternating sequence has 3 inside and 4 outside edges. Flipping changes size by 4−3=1.
C03. How many distinct perfect matchings does the labeled complete graph K₆ have?
A. 15 B. 6 C. 30 D. 720
Answer: A
A: Choose the partner of one fixed vertex in 5 ways, then pair the remaining four in 3 ways: 5·3=15. Equivalently 6!/(2³·3!).
B: The number of vertices does not count pair partitions; partner choices must be combined.
C: This double-counts the 15 edge sets; a matching has no ordering of its pairs.
D: 6! counts ordered vertex lists. Order within each pair and order among the three pairs must both be removed.
C04. A matching M in a finite simple graph has no augmenting path. Which conclusion is guaranteed?
A. M is perfect B. The graph is bipartite C. M is maximum D. M is the unique maximum matching
Answer: C
A: A one-edge matching in a triangle has no augmenting path but leaves one vertex uncovered.
B: The same triangle is not bipartite; the criterion does not require bipartiteness.
C: Berge’s criterion states that a matching is maximum exactly when no augmenting path exists.
D: Different maximum matchings can have the same size. In a triangle each of its three single edges is maximum.
C05. For the star K₁,₃, which statement is correct?
A. Its maximum matching has size 2 because it has four vertices. B. Its maximum matching has size 1 and no perfect matching exists. C. It has no matching because the center has degree 3. D. Every maximal matching is empty.
Answer: B
A: Even order gives only the upper bound 2, not existence; any two star edges share the center.
B: One edge is possible but two are impossible because all edges meet at the center. Two leaves remain exposed.
C: Any one edge is a valid matching regardless of the center’s degree.
D: The empty matching can be extended by adding any edge, so it is not maximal here.
C06. A four-vertex path has edge weights w(12)=1,w(23)=10,w(34)=1. Which pair of conclusions is correct?
A. Maximum cardinality is 10; maximum weight is 2. B. The maximum-weight matching must have two edges. C. All maximal matchings have equal total weight. D. Maximum cardinality is 2, but the maximum-weight matching has one edge of weight 10.
Answer: D
A: Cardinality counts selected edges, not a numerical edge weight.
B: The two-edge matching {12,34} weighs only 2, less than {23} of weight 10.
C: Both {23} and {12,34} are maximal, but their weights are 10 and 2.
D: The outer edges give the largest edge count 2. The middle edge alone gives total weight 10, larger than every alternative.
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