Augmenting Paths in General Graphs

Why Augmenting Paths Matter

A matching is a collection of edges that do not share vertices. The central problem is often to make such a collection as large as possible. An augmenting path gives a direct way to improve a matching: remove the matching edges on the path and add the other edges on it. The key point is that this criterion works in arbitrary graphs, not only in bipartite graphs.

Throughout, graphs are finite and simple. A matching \(M\) in \(G=(V,E)\) is a set of pairwise vertex-disjoint edges. A vertex is matched by \(M\) if it is incident with an edge of \(M\); otherwise it is unmatched (or exposed). A matching is maximum if no matching in the graph has more edges. It is maximal if no edge can be added to it while keeping a matching. Maximum means largest cardinality; maximal means only that no single addition is possible.

On an augmenting path, the first and last edges must lie outside \(M\). Thus the path has an odd number of edges, with one more edge outside \(M\) than inside it. Replacing the matching edges on the path by the other path edges increases the matching’s size by exactly one. This operation is called augmentation.

Flipping an Augmenting Path

Proof. Write the edges of \(P\), in order, as \(e_1,\ldots,e_{2k+1}\). Since \(P\) alternates and its endpoints are unmatched, \(e_1,e_3,\ldots,e_{2k+1}\) are outside \(M\), while \(e_2,e_4,\ldots,e_{2k}\) are in \(M\). There are \(k+1\) edges outside \(M\) and \(k\) edges in \(M\) on the path. After the replacement, each internal vertex of \(P\) is incident with exactly one retained path edge: its two path edges consist of one edge of each type, and the replacement keeps exactly one. Each endpoint gains one kept edge and had no edge of \(M\) incident with it. No vertex outside \(P\) is affected. The resulting edge set is therefore a matching, and its size changes by \((k+1)-k=1\). \(\square\)

Berge’s Criterion

Proof. First suppose \(M\) has an augmenting path. By the proposition, augmenting along it produces a matching with \(|M|+1\) edges. Therefore \(M\) is not maximum. This proves that every maximum matching has no augmenting path.

For the converse, suppose \(M\) is not maximum. Because the graph is finite, there is a matching \(M'\) with \(|M'|>|M|\). Consider the graph with vertex set \(V\) and edge set \(M\triangle M'\), where \(M\triangle M'\) consists of edges belonging to exactly one of \(M\) and \(M'\). At each vertex there is at most one incident edge from \(M\) and at most one from \(M'\). Consequently each vertex has degree at most two in this graph. If a vertex has degree two, one incident edge belongs to \(M\setminus M'\) and the other to \(M'\setminus M\). Thus the edges alternate between the two matchings along each component containing edges.

Each such component is a path or a cycle: starting at a vertex of degree one and following the only unused forward edge gives a path component; if there is no degree-one vertex, following edges in the finite component returns to the starting vertex and gives a cycle. On a cycle, alternation gives equal numbers of edges from \(M\) and \(M'\). On a path, the difference between the number from \(M'\) and the number from \(M\) is \(0\), \(1\), or \(-1\). Since the total number of edges of \(M'\) exceeds that of \(M\), at least one path component has one more edge from \(M'\) than from \(M\). Its edges alternate, its first and last edges belong to \(M'\setminus M\), and its length is odd.

The endpoints of this path are unmatched by \(M\). Indeed, each endpoint has just one incident edge in \(M\triangle M'\), and that edge belongs to \(M'\setminus M\). If an endpoint were incident with an edge of \(M\), that edge could not be another edge in the symmetric difference, since the endpoint has degree one there. It would therefore have to belong to both \(M\) and \(M'\). But that common edge and the incident \(M'\setminus M\) edge would share an endpoint, contradicting that \(M'\) is a matching. Hence the path is an augmenting path for \(M\). We have proved that if \(M\) is not maximum, it has an augmenting path. Together, the two directions establish the criterion. \(\square\)

The proof gives a structural reason the criterion applies to general graphs. The symmetric difference of two matchings separates their differing edges into alternating paths and cycles. Cycles contribute equally many edges to both matchings; a larger matching must gain an edge on at least one path, and that path is augmenting for the smaller matching.

Examples in General Graphs

A Common Mistake

Not every alternating path increases the size of a matching when its edges are flipped. The endpoint condition matters. For example, let \(G\) have \(V=\{1,2,3\}\), \(E=\{12,23\}\), and \(M=\{12\}\). The path \(1,2,3\) is alternating: \(12\) is in \(M\) and \(23\) is outside \(M\). But it is not augmenting, because vertex \(1\) is matched.

A mistaken calculation might say that flipping gives two edges, \(23\) and \(12\), and hence increases the size. This is not a valid matching: the two edges share vertex \(2\). The correct flip deletes \(12\) and adds \(23\), producing \(\{23\}\), which has size \(1\), the same as \(M\). In general, an alternating path guarantees an increase only when both endpoints are unmatched; those endpoints make the alternating sequence begin and end with edges outside the matching.

Berge’s criterion is an existence test, not by itself a search procedure. It says exactly what distinguishes a maximum matching from a smaller one: the smaller matching has an augmenting path. In practice, locating such a path is a separate task. The criterion remains useful even when that task is difficult, because it gives a precise certificate for why a matching is not yet maximum and tells us how to improve it.