When Is a Matching Maximum?
A matching is a set of edges with no shared endpoints. A matching is maximum if no matching in the graph has more edges; this is stronger than being maximal, which only means that no additional edge can be added while retaining a matching. An augmenting path gives a direct way to improve a matching. Berge’s theorem says that this local obstruction is also a complete test: a matching is maximum precisely when it has no augmenting path.
All graphs here are finite and simple. A path is a sequence of distinct vertices in which consecutive vertices are adjacent. Fix a matching \(M\). A path is alternating with respect to \(M\) if its edges alternate between edges in \(M\) and edges outside \(M\). An \(M\)-augmenting path is an alternating path whose two endpoints are unmatched by \(M\). In particular, an augmenting path begins and ends with edges outside \(M\).
Why Flipping an Augmenting Path Works
Suppose an \(M\)-augmenting path has \(2k+1\) edges. Because it alternates and begins and ends outside \(M\), it contains \(k\) edges of \(M\) and \(k+1\) edges outside \(M\). Flipping it therefore replaces \(k\) matching edges by \(k+1\) edges. At each internal vertex, exactly one of the two incident path edges is in the new matching. Each endpoint was unmatched and receives one path edge. No vertex outside the path is affected.
Proof. Write \(M'=(M\setminus E(P))\cup(E(P)\setminus M)\). Along \(P\), the edges alternate, starting and ending outside \(M\). Thus each internal vertex is incident to one added edge and one removed edge, and each endpoint is incident to one added edge and no edge of \(M\). Hence the edges retained or added in \(M'\) do not share endpoints with one another or with unchanged edges of \(M\). So \(M'\) is a matching. If \(P\) has \(2k+1\) edges, it has \(k\) edges in \(M\) and \(k+1\) outside \(M\), giving \(|M'|=|M|-k+(k+1)=|M|+1\). \(\square\)
Worked Example: Flipping an Augmenting Path
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,23,34,45,56\}\). Take \(M=\{23,45\}\). The path \(1,2,3,4,5,6\) has edges \(12,23,34,45,56\), which alternate outside \(M\), inside \(M\), outside \(M\), inside \(M\), outside \(M\). Its endpoints \(1\) and \(6\) are unmatched by \(M\), so it is an augmenting path.
Flip its edges: remove \(23\) and \(45\), and add \(12\), \(34\), and \(56\). The result is \(M'=\{12,34,56\}\). These three edges have pairwise disjoint endpoints, so \(M'\) is a matching. The sizes are \(|M|=2\) and \(|M'|=3=2+1\).
Check: \(M'\) covers all six vertices exactly once, so it is a matching of size \(3\). No matching on six vertices can have more than \(6/2=3\) edges, since each matching edge uses two distinct vertices. Thus \(M'\) is maximum, and the size calculation agrees with the lemma.
The Structure of a Symmetric Difference
Proof. At any vertex, at most one edge of \(M\) and at most one edge of \(N\) can be incident, since each set is a matching. Therefore at most two edges of \(M\triangle N\) meet at any vertex. If two such edges meet, one belongs to \(M\setminus N\) and the other to \(N\setminus M\): two edges from the same matching cannot meet. Thus the edges alternate along each component. A finite connected graph with maximum degree at most two and at least one edge is a path if it has a vertex of degree one, and otherwise is a cycle. On a cycle the alternating edge types occur equally often. On a path, the edge types either occur equally often or the type at one end occurs once more. This proves the claims. \(\square\)
Edges common to \(M\) and \(N\) do not appear in \(M\triangle N\). They do not affect the comparison of sizes: removing the common edges from both matchings leaves \(|M|-|N|\) unchanged. Consequently, if \(|N|>|M|\), the components of \(M\triangle N\) must include a path with one more edge from \(N\setminus M\) than from \(M\setminus N\). Cycles and balanced paths contribute zero to the size difference, and a path with one more \(M\)-edge would contribute negatively.
Such a path starts and ends with edges of \(N\setminus M\). Its endpoints are unmatched by \(M\). Indeed, each endpoint has just one incident edge in \(M\triangle N\), an edge of \(N\setminus M\). If an \(M\)-edge also met that endpoint, it could not be a common edge (that would conflict with the \(N\)-edge there); it would instead be an edge of \(M\setminus N\), giving another incident edge in the symmetric difference. That contradicts the endpoint having degree one. The path is therefore an \(M\)-augmenting path.
Berge’s Theorem
Proof. First suppose there is an \(M\)-augmenting path. By the flipping lemma, flipping it gives a matching of size \(|M|+1\). Therefore \(M\) is not maximum.
Conversely, suppose \(M\) is not maximum. By the definition of maximum, there is a matching \(N\) with \(|N|>|M|\). Consider the components containing edges in \(M\triangle N\). The common edges of \(M\) and \(N\) cancel when their sizes are compared, so the total difference is accounted for by these components. By the symmetric-difference lemma, each component is a path or cycle whose contribution to \(|N|-|M|\) is \(0\), \(1\), or \(-1\). Since the total is positive, at least one component contributes \(1\). That component is a path with one more \(N\)-edge than \(M\)-edge. As shown above, it starts and ends with \(N\setminus M\) edges and has endpoints unmatched by \(M\). Its edges alternate, so it is an \(M\)-augmenting path. We have proved both implications. \(\square\)
Worked Example: Finding an Augmenting Path in the Symmetric Difference
Let \(V=\{1,2,3,4,5,6,7,8\}\) and \(E=\{12,23,34,41,56,67,78\}\). Consider the matchings \(M=\{12,34,67\}\) and \(N=\{23,41,56,78\}\). Each is a matching: the edges in \(M\) have disjoint endpoints, and those in \(N\) also have disjoint endpoints.
There are no common edges, so \(M\triangle N=E\). Its components are the cycle \(1,2,3,4,1\), whose edges alternate between \(M\) and \(N\), and the path \(5,6,7,8\), whose edges are \(56\in N\), \(67\in M\), and \(78\in N\). The cycle contributes two edges from each matching. The path contributes two from \(N\) and one from \(M\). Accordingly, \(|M|=3\), \(|N|=4\), and the path is an \(M\)-augmenting path: its endpoints \(5\) and \(8\) are unmatched by \(M\).
Flipping the path removes \(67\) and adds \(56,78\), giving \(M'=\{12,34,56,78\}\), of size \(3-1+2=4\). Its edges have disjoint endpoints and cover all eight vertices. Thus it is a matching; no matching on eight vertices can have more than \(8/2=4\) edges. This independently confirms that \(M'\) is maximum.
Worked Example: No Augmenting Path in Two Disjoint Paths
Let \(V=\{a,b,c,d,e,f\}\) and \(E=\{ab,bc,de,ef\}\), so \(G\) is the disjoint union of the paths \(a,b,c\) and \(d,e,f\). Set \(M=\{ab,de\}\). The unmatched vertices are \(c\) and \(f\). Any path joining them would have to pass between the two components, but there is no edge between the components. Within each component there is only one unmatched vertex. An augmenting path needs two unmatched endpoints, so no \(M\)-augmenting path exists.
By Berge’s theorem, \(M\) is maximum. This can also be checked directly: each three-vertex component can contain at most one matching edge, because two disjoint edges would require four distinct vertices. Thus every matching in \(G\) has at most \(1+1=2\) edges, and \(M\) has exactly two.
Check: The graph has six vertices, so the general bound \(|M|\le 6/2=3\) alone would not certify maximal size. The sharper component-by-component bounds give at most one edge in each component, hence at most two in total; \(M\) attains that bound.
Common Pitfall: Alternating Does Not Mean Augmenting
An alternating path is not necessarily an augmenting path. The endpoints must both be unmatched by the chosen matching. For example, let \(V=\{1,2,3,4,5\}\), \(E=\{12,23,34,45\}\), and \(M=\{12,34\}\). The path \(1,2,3,4,5\) alternates: its edges are \(12\in M\), \(23\notin M\), \(34\in M\), and \(45\notin M\). But vertex \(1\) is matched, so this path is not augmenting.
A mistaken count might claim that flipping this alternating path increases the size by one. In fact, the flip removes \(12,34\) and adds \(23,45\), so the new matching is \(\{23,45\}\), of size \(2-2+2=2\), not \(3\). The path has two edges in \(M\) and two outside \(M\), and its endpoints are not both unmatched. The augmenting-path condition is what guarantees one more added edge than removed edge.
Berge’s theorem is useful because it turns an optimality question into a structural one. To prove that a matching is not maximum, it is enough to find one augmenting path. To prove that it is maximum, it is enough to establish that no such path exists. The symmetric difference explains why this test cannot miss a larger matching: any larger matching would supply an augmenting path.
Check Your Understanding
Use the definitions and theorem to answer these questions.
- In a matching of size \(4\), an augmenting path has \(7\) edges. How many of its edges are in the matching, and what is the size after flipping?
- For two matchings \(M,N\), why can a cycle component of \(M\triangle N\) not account for a positive difference \(|N|-|M|\)?
- Can an alternating path have one endpoint matched and the other unmatched? Give a small example or explain why not.
- Suppose a matching \(M\) has no augmenting path. What does Berge’s theorem imply about every other matching \(N\)?
- For \(V=\{1,2,3,4\}\), \(E=\{12,23,34\}\), and \(M=\{23\}\), identify an \(M\)-augmenting path and compute the matching obtained by flipping it.