Two Different Meanings of “Cannot Be Improved”
A matching is a collection of edges that do not share endpoints. There are two natural questions about a matching: can another edge be added to it, and is its size as large as possible? These questions are not equivalent. A matching may be impossible to enlarge by simply adding an edge, yet a different choice of edges may produce a larger matching.
All graphs in this tutorial are finite and simple. For \(G=(V,E)\), a matching \(M\subseteq E\) is a set of pairwise vertex-disjoint edges: no two edges in \(M\) share an endpoint. A vertex is saturated by \(M\) if it is an endpoint of an edge in \(M\); otherwise it is unsaturated. The size of \(M\) is \(|M|\), the number of its edges.
“Maximal” is about inclusion: no edges can be added while keeping all the edges already in \(M\). “Maximum” is about cardinality: no matching anywhere in \(G\) has more edges. Since a finite graph has only finitely many edge subsets, at least one matching has largest size, and \(\nu(G)\) is well-defined. The empty set is a matching, including when the graph has no edges.
How to Test Maximality
The definition of maximality compares \(M\) with every matching that contains it. In practice, there is a local test: look for an edge whose two endpoints are both unsaturated.
Proof. First suppose that \(M\) is maximal. If an edge \(uv\in E\) had both endpoints unsaturated by \(M\), then \(uv\notin M\) and \(M\cup\{uv\}\) would still be a matching: the new edge would share no endpoint with any edge of \(M\). This would be a matching properly containing \(M\), contrary to maximality. Thus every edge has a saturated endpoint.
Conversely, suppose every edge has at least one endpoint saturated by \(M\). If \(M\) were not maximal, there would be a matching \(M'\) properly containing \(M\). Choose an edge \(e=uv\in M'\setminus M\). Because \(M'\) is a matching containing \(M\), neither endpoint of \(e\) can be incident with an edge of \(M\); otherwise \(e\) and that edge would share an endpoint in \(M'\). Thus both endpoints of \(e\) are unsaturated by \(M\), contradicting the assumption. Therefore \(M\) is maximal. \(\square\)
This test also explains why checking only the number of edges in \(M\) is not enough. Maximality depends on which vertices are saturated and on which edges join the remaining vertices. A matching is maximal precisely when its unsaturated vertices form an independent set: no two of them are adjacent.
Every Maximum Matching Is Maximal
Proof. Let \(M\) be maximum. If it were not maximal, there would be a matching properly containing \(M\). That matching would include at least one additional edge, so it would have size greater than \(|M|\). This contradicts the assumption that \(M\) has largest possible size. Hence \(M\) is maximal. The examples below show that a maximal matching need not be maximum. \(\square\)
A useful general upper bound comes directly from counting endpoints. A matching of size \(k\) uses \(2k\) distinct vertices, so \(2k\le |V|\). Thus every matching satisfies \(|M|\le \lfloor |V|/2\rfloor\). When a matching reaches this bound, it is maximum. This bound need not be sharp for every graph; the available edges may impose a smaller limit.
Worked Example: A Maximal Matching That Is Not Maximum
Let \(G\) have vertex set \(V=\{1,2,3,4\}\) and edge set \(E=\{12,23,34\}\), so \(G\) is the path \(P_4\). Consider \(M=\{23\}\).
The edge \(23\) saturates vertices \(2\) and \(3\), leaving \(1\) and \(4\) unsaturated. The edges not in \(M\) are \(12\) and \(34\). Edge \(12\) has the saturated endpoint \(2\), and edge \(34\) has the saturated endpoint \(3\). The maximality test therefore shows that \(M\) is maximal. Equivalently, the only unsaturated vertices, \(1\) and \(4\), are not adjacent.
However, \(M_1=\{12,34\}\) is also a matching: its two edges have no common endpoint. It has size \(2\), while \(|M|=1\), so \(M\) is not maximum. To verify the size of \(M_1\) is optimal, any matching in a graph on four vertices has size at most \(\lfloor 4/2\rfloor=2\). Therefore \(\nu(G)=2\), and \(M_1\) is maximum.
Check: \(M\) is maximal by the edge test, but it cannot be maximum because the explicitly listed matching \(M_1\) has more edges. Also, \(M_1\) reaches the upper bound of \(2\), so no larger matching exists.
The key difference is that a proper enlargement must keep every edge of \(M\). In the example, neither \(12\) nor \(34\) can be added to \(\{23\}\), because each shares an endpoint with \(23\). The larger matching is obtained by choosing a different set of edges, not by adding an edge to the original matching.
Worked Example: Different Maximal Sizes in a Six-Vertex Path
Let \(G\) have vertex set \(V=\{1,2,3,4,5,6\}\) and edge set \(E=\{12,23,34,45,56\}\). Consider \(M=\{23,45\}\). Its edges are disjoint, and the saturated vertices are \(2,3,4,5\); the unsaturated vertices are \(1,6\).
Check every edge. Edge \(12\) meets saturated vertex \(2\); edge \(23\) is in \(M\); edge \(34\) meets saturated vertices \(3\) and \(4\); edge \(45\) is in \(M\); and edge \(56\) meets saturated vertex \(5\). Every edge therefore has a saturated endpoint, so \(M\) is maximal. In particular, the fact that \(1\) and \(6\) are both unsaturated does not prevent maximality: there is no edge \(16\).
Now take \(N=\{12,34,56\}\). These three edges are pairwise disjoint, so \(N\) is a matching of size \(3\). Since \(G\) has six vertices, the endpoint bound gives \(|M'|\le\lfloor 6/2\rfloor=3\) for every matching \(M'\). Consequently \(\nu(G)=3\), and \(N\) is maximum. It is also maximal, as every maximum matching must be.
Check: \(M\) has size \(2\), while \(N\) has size \(3\), and the upper bound proves that size \(3\) is optimal. The two maximal matchings have different sizes; maximality alone does not determine the matching number.
When the Graph Structure Forces a Smaller Maximum
The endpoint bound uses only the number of vertices. A graph may have many vertices but too few mutually disjoint edges to reach that bound. In such cases, a structural argument is needed to prove that a matching is maximum. For example, if every edge is incident with one particular vertex, then any matching can contain at most one edge, regardless of how many other vertices there are.
Worked Example: A Star with an Isolated Vertex
Let \(G\) have vertex set \(V=\{a,b,c,d,e\}\) and edge set \(E=\{ab,ac,ad\}\). This is a star on \(a,b,c,d\) together with the isolated vertex \(e\). Consider \(M=\{ab\}\).
The matching \(M\) saturates \(a\) and \(b\). The other edges, \(ac\) and \(ad\), each meet the saturated vertex \(a\), so the edge test proves that \(M\) is maximal. The isolated vertex \(e\) creates no additional edge and does not change this test.
Moreover, every edge of \(G\) is incident with \(a\). Two distinct edges therefore share \(a\), so no matching can contain two edges. Since \(M\) contains one edge, the largest possible size is \(\nu(G)=1\); \(M\) is maximum as well as maximal.
The empty matching \(\varnothing\) is not maximal here, because any one of \(ab,ac,ad\) can be added. In contrast, if a graph has no edges, then its only matching is \(\varnothing\), and that matching is both maximal and maximum, of size \(0\).
Check: There are three edges, but they all share \(a\), so the maximum matching size is \(1\), not the vertex-count bound \(\lfloor 5/2\rfloor=2\). The exhibited matching reaches the structural upper bound of \(1\).
Common Pitfalls and Why the Distinction Matters
Mistake: treating “maximal” as “largest.” In the six-vertex path above, one might say that \(\{23,45\}\) is not maximal because the matching \(\{12,34,56\}\) is larger. That comparison does not test maximality: the larger matching does not contain \(\{23,45\}\). The correction is to check whether an edge can be added while retaining both \(23\) and \(45\). The remaining edges are \(12,34,56\); each meets a vertex already saturated by \(M\). Thus \(\{23,45\}\) is maximal, although it is not maximum.
Mistake: requiring every vertex to be saturated. A maximal matching need not cover all vertices. In the six-vertex path, the maximal matching \(\{23,45\}\) leaves vertices \(1\) and \(6\) unsaturated. Maximality requires only that no edge can be added, not that every vertex be used. A matching that saturates every vertex is called a perfect matching; that is a stronger condition and is not part of the definition of maximality.
The distinction matters whenever a procedure builds a matching by adding available edges and stops when no further edge can be inserted. Its result is maximal, but that fact alone does not certify that the result has the greatest possible size. To prove maximum size, one must compare with an upper bound or otherwise rule out every larger matching. In the examples, endpoint counts and the fact that all star edges share a center provide such checks.
Check Your Understanding
For each question, distinguish whether the issue is inclusion, size, or both.
- In the graph \(V=\{1,2,3,4\}\), \(E=\{12,23,34\}\), test whether \(\{12\}\) is maximal. Is it maximum?
- Give a precise reason why every maximum matching is maximal.
- State the edge test for maximality, and explain why it is equivalent to saying that the unsaturated vertices form an independent set.
- In the star with center \(a\) and leaves \(b,c,d\), why can no matching have more than one edge?
- Can the empty matching be maximal in a graph with at least one edge? Justify your answer.