Augmenting Paths and the Edge-Flipping Operation

From Alternation to Augmentation

A matching pairs vertices so that no vertex is used more than once. An alternating path moves back and forth between edges in a matching and edges outside it. When the path starts and ends at unmatched vertices, exchanging the two types of edges frees the vertices that were paired along the path and pairs its endpoints instead. The result is a larger matching.

All graphs in this tutorial are finite and simple. A path is a sequence of distinct vertices \(v_0,v_1,\ldots,v_\ell\) such that consecutive vertices are adjacent; its length is \(\ell\), the number of its edges. A matching \(M\subseteq E(G)\) is a set of edges no two of which share an endpoint. A vertex is matched by \(M\) if it is incident to an edge of \(M\), and is unmatched otherwise. The size of the matching is \(|M|\).

Positive length matters: a one-vertex path has no edges, so alternation would hold vacuously, but changing the matching along it would do nothing. The definition rules out that case. Since a path has distinct vertices, any positive-length path already has distinct endpoints; the explicit endpoint condition emphasizes that both ends are unmatched.

Why the Path Has the Right Edge Pattern

Let \(P=v_0v_1\cdots v_\ell\) be an augmenting path. Its first edge \(v_0v_1\) is not in \(M\): if it were in \(M\), then \(v_0\) would be matched. Likewise, its last edge \(v_{\ell-1}v_\ell\) is not in \(M\), because \(v_\ell\) is unmatched. The edges alternate, beginning and ending outside \(M\), so the path has one more edge outside \(M\) than inside \(M\).

Proof. Write the edge sequence of the positive-length path as \(e_1,\ldots,e_\ell\). The first and last edges are outside \(M\), and consecutive edges alternate between outside and inside \(M\). Thus the sequence starts and ends with an outside edge. Alternation implies that the positions \(1,3,5,\ldots\) are exactly the positions of edges outside \(M\), while the even positions are exactly the positions of edges in \(M\). Because the last position is outside \(M\), \(\ell\) is odd; write \(\ell=2k+1\) with \(k\geq0\). There are \(k+1\) odd positions and \(k\) even positions, giving the claimed counts. Since the path has positive length, the case \(k=0\) is a single edge joining two distinct unmatched vertices. \(\square\)

The edge exchange can now be described precisely. Remove from \(M\) the path edges that belong to \(M\), and add the path edges that do not belong to \(M\). Keep every edge of \(M\) outside the path unchanged.

The Edge-Flipping Result

Proof. Write \(P=v_0v_1\cdots v_{2k+1}\), using the lemma. We first show that \(M'\) is a matching. The endpoints \(v_0\) and \(v_{2k+1}\) were unmatched by \(M\); each is incident to exactly one path edge, which is outside \(M\) and is added to \(M'\). No edge of \(M\) outside \(P\) is incident to either endpoint, since that would have matched it in \(M\). Thus each endpoint is incident to exactly one edge of \(M'\).

Every internal vertex \(v_i\), where \(1\leq i\leq 2k\), is incident to two consecutive path edges. Since the path alternates, exactly one of those two edges belongs to \(M\) and the other does not. The edge in \(M\) is removed, and the edge outside \(M\) is added, so \(v_i\) is incident to exactly one of these path edges in \(M'\). No matching edge outside \(P\) can be incident to \(v_i\): it would share \(v_i\) with the path edge of \(M\), contradicting that \(M\) is a matching. Vertices not on \(P\) have no incident matching edge changed. Hence no two edges of \(M'\) share an endpoint, so \(M'\) is a matching.

For the size, \(P\) has \(k+1\) edges outside \(M\) and \(k\) edges in \(M\). The flip adds the former and removes the latter, so \(|M'|=|M|+(k+1)-k=|M|+1\). This includes \(k=0\): a single edge between two unmatched vertices is added, and the size increases by one. \(\square\)

This theorem is a local statement about a particular matching and a particular path. It proves that an augmenting path gives a larger matching, and therefore that the original matching is not maximum. It does not by itself establish that a matching with no augmenting path is maximum; that characterization is a separate result.

Worked Examples

Common Mistakes and the Limits of the Result

Mistake: allowing a zero-length augmenting path. If a path consisting of one unmatched vertex were allowed, its edge set would be empty. Flipping it would give \(M'=M\), not a matching larger by one. Requiring positive length and distinct unmatched endpoints prevents this failure. For a positive-length alternating path with unmatched endpoints, the first and last edges are outside \(M\), which is why its length is odd.

Mistake: adding the outside edges without removing the inside edges. In the first worked example, adding \(ab\) and \(cd\) to \(M=\{bc\}\) without removing \(bc\) would produce \(\{ab,bc,cd\}\). This is not a matching: \(ab\) and \(bc\) both use \(b\), while \(bc\) and \(cd\) both use \(c\). The correction is to remove the matched path edge \(bc\) as the two outside edges are added. Then \(\{ab,cd\}\) is a matching.

Do not confuse augmentation with an optimality test. Finding an augmenting path proves that a matching is not maximum, because the flip gives a larger one. The theorem proved here does not say that every nonmaximum matching must have an augmenting path. Establishing that converse requires an additional argument.

The edge-flipping operation is useful because it turns a path with a simple alternating pattern into a concrete improvement. The validity check is essential: internal vertices exchange their one matched path edge for the other path edge, while the two previously unmatched endpoints each gain one edge. Counting the two types of path edges then gives the exact increase, not merely an assertion that the matching becomes larger.