Matchings and the Vertices They Cover
A matching selects edges that do not compete for endpoints. This simple requirement makes matchings useful in assignment and pairing problems: each selected edge represents one pair, and no vertex is assigned to two pairs. In a general graph, there need not be a bipartition into two classes, so it is important to define matching notions without relying on one.
Throughout, graphs are finite and simple: they have no loops or multiple edges. If \(G=(V,E)\), a matching is a subset of \(E\). Two edges are disjoint when they have no common endpoint. A vertex is covered by a matching if it is an endpoint of one of its edges; otherwise it is exposed (also called unmatched) with respect to that matching. The words “covered” and “exposed” always refer to the particular matching under discussion.
Maximum and maximal express different comparisons. “Maximum” compares sizes across all matchings in the graph. “Maximal” asks whether the particular matching can be enlarged by adding edges while keeping all its existing edges. A maximal matching need not have the greatest possible size.
Since \(G\) is finite, it has finitely many subsets of edges, and therefore finitely many matchings. The empty set of edges is a matching, including when \(E=\varnothing\). Consequently at least one matching has greatest size, so a maximum matching exists. If \(V=\varnothing\), the empty matching covers every vertex vacuously and is perfect. If \(V\) is nonempty and has an isolated vertex, no matching can cover that vertex, so no perfect matching exists.
Two Useful Tests
Proof. First suppose \(M\) is maximum. If it were not maximal, a matching \(M'\) would strictly contain \(M\). Then \(|M'|>|M|\), contradicting the fact that \(M\) has greatest size. Thus \(M\) is maximal.
For the second assertion, suppose an edge \(uv\) has both endpoints exposed with respect to \(M\). Since neither endpoint belongs to any edge of \(M\), adding \(uv\) creates no shared endpoint with an edge already in \(M\). Hence \(M\cup\{uv\}\) is a larger matching, so \(M\) is not maximal.
Conversely, suppose \(M\) is not maximal. Then some matching \(M'\) strictly contains \(M\), so it contains an edge \(uv\) not in \(M\). Because \(M'\) is a matching containing \(M\), neither \(u\) nor \(v\) can be an endpoint of an edge in \(M\); otherwise that edge and \(uv\) would share an endpoint in \(M'\). Thus \(uv\) joins two vertices exposed with respect to \(M\). This proves both directions. \(\square\)
A quick consequence of the endpoint condition is that any matching \(M\) in a graph of order \(n=|V|\) covers exactly \(2|M|\) vertices: each edge has two endpoints, and pairwise disjoint edges have no endpoints in common. Therefore the number of exposed vertices is \(n-2|M|\). In particular, the empty matching exposes all vertices, while a perfect matching exposes none.
Proof. Let \(M\) be perfect, and let \(N\) be any matching in the same graph. Since \(M\) covers all \(n\) vertices using disjoint edges, \(2|M|=n\). Since \(N\) also consists of disjoint edges with endpoints in \(V\), \(2|N|\le n\). It follows that \(|N|\le n/2=|M|\). Thus no matching has greater size than \(M\), so \(M\) is maximum. This also applies when \(V=\varnothing\): both matching sizes are zero. \(\square\)
Worked Examples
Worked Example: A Maximal Matching That Is Not Maximum
Let \(G=(V,E)\) have \(V=\{1,2,3,4\}\) and \(E=\{12,23,34\}\), the path on four vertices. Consider \(M=\{23\}\). Its endpoints are \(2\) and \(3\), so vertices \(1\) and \(4\) are exposed. There is no edge \(14\) in \(E\); hence no edge joins the two exposed vertices. By the maximality test, \(M\) is maximal.
However, \(N=\{12,34\}\) is also a matching, since its two edges have no common endpoint. It has size \(2\), whereas \(|M|=1\), so \(M\) is not maximum. To verify that \(N\) is maximum, note that any matching in a graph on four vertices has at most \(4/2=2\) edges, because each matching edge uses two distinct vertices. The matching \(N\) attains that bound, so \(\nu(G)=2\). It covers all four vertices and is perfect.
Check: \(M\) cannot be enlarged by adding one of the listed edges: \(12\) shares vertex \(2\) with \(23\), and \(34\) shares vertex \(3\) with \(23\). Yet the different matching \(N\) has an extra edge. This is precisely why “maximal” does not mean “maximum.”
Worked Example: A Maximum Matching in an Odd Cycle
Let \(G=(V,E)\) have \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45,51\}\), the cycle \(C_5\). Take \(M=\{12,34\}\). These edges have disjoint endpoints, so \(M\) is a matching. Vertices \(1,2,3,4\) are covered, and vertex \(5\) is exposed.
Any matching in this graph uses two distinct vertices for each of its edges. Three matching edges would require six distinct vertices, but \(G\) has only five. Therefore every matching has size at most \(2\). Since \(M\) has size \(2\), it is maximum and \(\nu(G)=2\). It is also maximal, as the theorem guarantees; directly, its only exposed vertex is \(5\), and no edge can join that vertex to itself.
The exposed vertex depends on the choice of maximum matching. For example, \(M'=\{23,45\}\) is a matching of size \(2\), and it exposes vertex \(1\). Its size is also maximum by the same six-vertices bound. Neither \(M\) nor \(M'\) is perfect, because each leaves one vertex uncovered.
Check: The two listed edges in \(M\) cover four distinct vertices, so the count of exposed vertices is \(5-2(2)=1\), agreeing with the direct identification of vertex \(5\). The example shows that a maximum matching need not be perfect in a nonbipartite graph.
Worked Example: Maximum and Maximal Matchings in \(K_5\)
Let \(G=K_5\), with \(V=\{1,2,3,4,5\}\) and \(E=\{12,13,14,15,23,24,25,34,35,45\}\). This is a complete graph: every pair of distinct vertices is an edge. Consider \(M=\{12,34\}\). It is a matching of size \(2\), and vertex \(5\) is exposed.
A matching of size \(3\) would need six distinct endpoints, which cannot be chosen from five vertices. Thus every matching has size at most \(2\), and \(M\) is maximum. It is maximal as well. Indeed, only vertex \(5\) is exposed, so there is no edge with both endpoints exposed. There is no perfect matching in this example: a perfect matching would have to cover all five vertices in disjoint pairs, but three edges would require six vertices and two edges cover only four.
Check: \(M\) covers \(2(2)=4\) vertices, leaving \(5-4=1\) exposed. This agrees with the vertex list. The complete graph has many edges, but having many possible edges does not remove the limitation that matching edges cannot share endpoints.
Worked Example: A Perfect Matching in \(K_4\)
Let \(G=K_4\), with \(V=\{1,2,3,4\}\) and \(E=\{12,13,14,23,24,34\}\). The set \(M=\{12,34\}\) is a matching: its edges have no common endpoint. It covers vertices \(1,2,3,4\), so it is perfect.
Because \(M\) has size \(2\) and \(G\) has only four vertices, no matching can have more than \(4/2=2\) edges. Thus \(M\) is maximum, in agreement with the proposition. It is maximal too: every vertex is already covered, so no edge can be added without sharing an endpoint with an edge of \(M\).
Check: The endpoints of \(12\) are \(1,2\), and those of \(34\) are \(3,4\). Together these are exactly the four vertices, each occurring once. Hence the matching is indeed perfect, not merely maximal.
Common Mistakes and Why the Distinctions Matter
Pitfall: treating “cannot add an edge” as “has maximum size.” On the path in the first example, one might incorrectly argue that \(M=\{23\}\) is maximum because every edge in \(E\) shares an endpoint with \(23\), so no edge can be added to \(M\). That calculation establishes maximality only. It does not compare \(M\) with other matchings. The correction is to exhibit and compare with \(N=\{12,34\}\): \(|N|=2>1=|M|\), so \(M\) is not maximum.
Pitfall: using “exposed” without specifying a matching. A vertex may be exposed by one matching and covered by another. In \(C_5\), vertex \(5\) is exposed by \(\{12,34\}\), while vertex \(1\) is exposed by \(\{23,45\}\). Exposure is not an intrinsic property of a vertex in the graph; it is a property relative to a chosen matching.
The distinctions are useful whenever a problem asks for a pairing. A maximal matching describes a pairing that cannot be extended by simply adding one more pair. A maximum matching solves the optimization problem of using as many pairs as possible. A perfect matching is stronger still: it pairs every vertex. The implications established here are that perfect implies maximum, and maximum implies maximal. The reverse implications do not hold in general, as the examples show.
In a bipartite graph, Hall’s condition can provide a criterion for a perfect matching, but that criterion assumes a bipartition. The definitions and elementary comparisons in this tutorial apply to arbitrary finite simple graphs, including odd cycles and complete graphs. For a general graph, one should first identify which question is being asked—whether a matching can be enlarged, whether its size is greatest, or whether it covers every vertex—before choosing a test or making a claim.
Check Your Understanding
For each question, name the matching explicitly and distinguish size from coverage.
- In the path \(P_4\) with edges \(12,23,34\), is \(\{23\}\) maximal? Is it maximum? Justify both answers.
- In \(C_5\) with edges \(12,23,34,45,51\), list the exposed vertices for the matching \(\{12,34\}\). Is that matching perfect?
- Prove directly from the endpoint condition that a matching of size \(k\) covers exactly \(2k\) vertices.
- Can a maximal matching be perfect? Can a maximum matching fail to be perfect? Give examples or explain why.
- In \(K_5\), why can no matching have three edges, even though every pair of distinct vertices is adjacent?