Matchings and Augmenting Paths

The question

Three sensors, $p,q,t$, need three distinct sockets, $r,s,u$. Sensor $p$ can use $r$ or $s$; $q$ can use only $r$; $t$ can use $s$ or $u$. A technician connects $p$ to $r$ and $t$ to $s$. Now the unused sensor $q$ cannot reach the unused socket $u$. Is two the best possible?

No: move $t$ to $u$, move $p$ to $s$, and connect $q$ to $r$. All three work. The technician's mistake was treating occupied connections as permanent. The repair changes several decisions, but improves the total by just one. We want a precise description of such repairs and a proof that, whenever a better pairing exists, a repair of that form exists too.

Throughout this lesson graphs are finite, simple and undirected. A path has distinct vertices; its length is its number of edges. We use edge sets rather than ordered pairs when discussing matchings: $pr$ and $rp$ name the same edge. The definitions and Berge's theorem below apply also to graphs that are not bipartite; only the final search procedure needs a bipartition.

Before pairing: the model and the words

A matching $M$ of a graph $G$ is a subset of $E(G)$ such that no two edges in $M$ share a vertex. A vertex incident to an edge of $M$ is $M$-saturated. Otherwise it is $M$-unsaturated, or free. An occupied vertex has exactly one partner in the matching. A perfect matching saturates every vertex. A graph with a perfect matching therefore has an even number of vertices, since its vertices are partitioned into pairs. Having an even number is necessary, but not sufficient: an isolated vertex cannot be saturated.

A matching is maximal if no edge can be added while keeping all its existing edges. It is maximum if no matching of the graph has more edges. The size of a maximum matching is the matching number ${\alpha }^{\prime }(G)$. Maximum refers to cardinality; maximal refers to containment. Every maximum matching is maximal: an addable edge would contradict its largest size. The converse fails in our sensor graph.

For $M=\{pr,ts\}$ every graph edge touches a saturated vertex, so none can be added. Yet $\{qr,ps,tu\}$ has three edges. Thus $M$ is maximal and not maximum. A perfect matching is maximum because any matching uses two distinct vertices per edge and hence has at most $|V(G)|/2$ edges. A maximum matching need not be perfect; it may leave vertices free even when no improvement is possible. These are separate properties, not alternative names.

The naive approach

One way to settle the example is to list every subset of its five edges and discard subsets with repeated endpoints. This small verification is deliberately brute force; it does not implement the constructive search the lab asks you to build.

from itertools import combinations

def edge(a, b):
    return frozenset((a, b))

def matching(es):
    vertices = set().union(*es) if es else set()
    return all(len(e) == 2 for e in es) and len(vertices) == 2 * len(es)

connections = [('p','r'), ('p','s'), ('q','r'), ('t','s'), ('t','u')]
E = {edge(a,b) for a,b in connections}
M = {edge('p','r'), edge('t','s')}
subsets = [set(c) for k in range(len(E)+1) for c in combinations(E,k)]
feasible = [c for c in subsets if matching(c)]
assert len(E) == 5 and len(subsets) == 32
assert matching(M) and len(M) == 2
assert all(not matching(M | {e}) for e in E-M)
assert max(map(len,feasible)) == 3

For $m$ edges this method considers $2^m$ subsets, including many that fail for the same local reason. More importantly, the list explains only this instance. A proof that works for every graph needs a structural reason a larger matching can replace the current one. The key is to compare two solutions only where they differ, rather than enumerate all solutions.

Trace a repair: alternating and augmenting paths

An $M$-alternating path has edges alternating between $M$ and $E(G)⧵M$. An $M$-augmenting path is a nonempty $M$-alternating path whose two endpoints are $M$-unsaturated. Since no matching edge meets either endpoint, the first and last edges are outside $M$. The length is odd. If it contains $h$ edges of $M$, it contains $h+1$ outside $M$.

In the sensor graph, take the path

$$q,r,p,s,t,u.$$

Its five edges have membership pattern outside, inside, outside, inside, outside. It proposes three new connections and releases two old ones. In physical terms the movement travels backward through owners of occupied sockets before reaching an unused socket.

The symmetric difference of sets $A,B$ is $A△B=(A⧵B)\cup (B⧵A)$: keep members of exactly one set. Augmenting along $P$ replaces $M$ by $M△E(P)$. It toggles every path edge and keeps all edges outside the path unchanged.

P = ['q','r','p','s','t','u']
path_edges = {edge(a,b) for a,b in zip(P,P[1:])}
repaired = M ^ path_edges
assert len(path_edges) == 5
assert repaired == {edge('q','r'),edge('p','s'),edge('t','u')}
assert matching(repaired) and len(repaired) == len(M)+1 == 3

Flip lemma. For every matching $M$ of a finite simple graph $G$ and every $M$-augmenting path $P$, $M△E(P)$ is a matching with $|M|+1$ edges.

Proof. Each internal vertex of $P$ meets two path edges, exactly one in $M$. Toggling removes that matching edge and installs the other. Because $M$ is a matching, no additional $M$-edge outside $P$ meets that vertex. Each endpoint has no incident $M$-edge at all, and receives one path edge. Vertices outside $P$ keep their original incidences. Consequently no vertex meets two edges in the new set. Its size rises by $(h+1)-h=1$. $◻$

Two matchings: the structure lemma

Structure lemma. For every pair of matchings $M,N$ of a finite simple graph $G$, each nontrivial component of the spanning subgraph $D=(V(G),M△N)$ is a path or an even cycle, with edges alternating between $M⧵N$ and $N⧵M$. The remaining components are isolated vertices.

Proof. At any vertex there is at most one incident edge from $M$ and at most one from $N$. Hence its degree in $D$ is at most two. At a vertex with two incident difference edges, those edges cannot both come from $M$, nor both from $N$: either would violate the corresponding matching. Thus they alternate. Consider a connected component with an edge. If it has a vertex of degree one, start there and follow the unique unused continuation. No branching is possible. A return to a previously visited vertex would create a cycle with an attached entry edge, giving degree at least three somewhere, or revisit the degree-one start, which is impossible. Finiteness therefore ends the traversal at another degree-one vertex. No vertex of the component can lie outside this path, since a connection to it would again need an extra incident edge. The whole component is a path.

If there is no degree-one vertex, every vertex in the nontrivial component has degree two. Following edges must eventually close a cycle, and no extra vertex can attach to that cycle without creating degree three. The component is exactly that cycle. On a cycle alternation must also hold where the last edge meets the first, so its length is even. $◻$

The word whole matters. A subpath of a component may omit a matching edge at its endpoint. The lemma describes components after shared edges have cancelled. Such shared edges cannot attach to a difference component: either endpoint of a shared edge already has its unique edge in both matchings, and meets no other edge of either one.

For a separate comparison, use a square and an unrelated edge. Matchings $A$ and $B$ choose opposite pairs on the square and share the unrelated edge. Their difference is just the square; the shared pair's vertices are isolated in the spanning difference graph.

A = {edge('v0','v1'),edge('v2','v3'),edge('v4','v5')}
B = {edge('v1','v2'),edge('v3','v0'),edge('v4','v5')}
assert matching(A) and matching(B)
cycle = ['v0','v1','v2','v3','v0']
assert A ^ B == {edge(a,b) for a,b in zip(cycle,cycle[1:])}
assert len(A ^ B) == 4 and len(A & B) == 1
assert not any('v4' in e or 'v5' in e for e in A ^ B)

Berge's theorem: a model proof

Proof. If an $M$-augmenting path exists, the flip lemma constructs a matching with one more edge. Thus a maximum matching has no such path.

For the converse, prove the contrapositive. Suppose $M$ is not maximum. Choose a matching $N$ with $|N|>|M|$, and decompose $M△N$ by the structure lemma. Shared edges contribute nothing to $|N|-|M|$. An even cycle contributes equally many edges of each matching. An even-length path also contributes equally many. An odd-length path contributes one extra edge from one matching or the other. Since the total contribution from $N$ exceeds that from $M$, at least one whole component is an odd path $P$ with one extra $N$-edge. Its first and last edges are in $N⧵M$.

We must prove both endpoints are $M$-unsaturated, not merely free within the drawn path. Let $x$ be either endpoint, and let $xy$ be its incident $N$-edge on $P$. Suppose an edge $xz$ of $M$ meets $x$. If $xz\notin N$, it belongs to $M△N$ and supplies a second component edge at $x$, contradicting that $x$ is an endpoint of the whole component. If $xz\in N$, then because $N$ is a matching and already contains $xy$, we have $z=y$. But then $xy$ is shared by both matchings, contradicting $xy\in N⧵M$. Both cases are impossible. Apply the argument independently to each endpoint. Thus $P$ alternates, has two unsaturated endpoints, and is $M$-augmenting. $◻$

Proof moves used here. Contrapositive changes “no repair implies largest” into “not largest produces a repair.” Decomposition breaks the difference into components whose edge counts are transparent. Averaging says a positive sum of component surpluses has a positive term; it does not say every component has a surplus. Case split rules out both possible memberships of a supposed endpoint matching edge.

Notice what this proof does not assume: $G$ is not required to be connected or bipartite, and $N$ need not be perfect. Any strictly larger matching is enough. The empty matching and isolated vertices cause no exception. When presenting the theorem in an assessed proof, state both directions and keep the endpoint argument visible; “the odd path augments” alone leaves its essential hypothesis unproved.

Alternating search in a bipartite graph

Now assume $G$ is an $X,Y$-bigraph: its vertices are partitioned into disjoint sets $X,Y$ and every edge joins the two sides. Direct each edge outside $M$ from $X$ to $Y$, and each edge of $M$ from $Y$ to $X$. Start an ordinary directed breadth-first search simultaneously from every unsaturated vertex of $X$.

Each discovered vertex gets one parent, and each root gets no parent. The parent paths alternate: every outward step from $X$ uses an edge outside $M$, and every step back from $Y$ uses that vertex's matching edge. A reached free vertex of $Y$ ends an augmenting path. Following parents gives a simple path, since each parent was discovered before its child.

Why does failure prove there is no augmenting path? Every augmenting path has odd length, so in a bigraph its free endpoints lie on opposite sides. Orient it from its endpoint in $X$. All its edges have the permitted direction. A complete directed search from all free $X$ vertices reaches its other endpoint. Thus if no free $Y$ is reached, no augmenting path exists anywhere. Berge then proves $M$ is maximum. Searching only one free root proves only that no repair starts there, unless it is the only root.

In our trace, the only root is $q$. The search follows $q\to r\to p\to s\to t\to u$. A socket does not branch back to every sensor that could use it: it goes back only to its current partner. Ordinary undirected reachability would forget this restriction and could report a route whose flip is invalid.

Bipartiteness makes the legal next kind of edge depend on the vertex's side, not on how it was reached. That is why one visited mark per vertex is enough. In a general graph this fixed-side description is unavailable; odd cycles require more care to find a simple augmenting path. Berge remains true there, but this bipartite search is not a general matching algorithm. The present module does not develop blossom contraction.

What the theorem buys, and what checking costs

An augmenting path is short evidence that a matching is not maximum. It has at most $n-1$ edges in a graph with $n$ vertices. Given adjacency lists, a matching and the path, one can build edge-membership and saturation sets and check distinct vertices, alternation and both endpoints in $O(n+m)$ expected time using expected constant-time hash operations, where $m=|E(G)|$. If those sets are already available, checking the path costs time linear in its length. These are checking costs, not bounds for finding paths in arbitrary graphs.

In a bipartite graph, constructing the directed search and exploring it costs $O(n+m)$ under the same adjacency-list and hashing model: every vertex is discovered once and every listed edge is inspected at most a constant number of times. Flipping takes linear time in the path length. Starting with an empty matching, each successful search adds one edge; there can be at most $k=min(|X|,|Y|)$ successes. Including a final failed search, this gives $O((k+1)(n+m))$ expected time for the straightforward implementation, with $O(n+m)$ space. This conservative form also covers isolated vertices and an edgeless graph.

Contrast the $2^m$ edge subsets of brute force: already twenty edges give over a million candidates, although one search still scans only the supplied vertices and edges.

assert 2**5 == 32 and 2**20 == 1_048_576

A failed complete bipartite search is evidence of maximum size that can be checked by rerunning that search. Module 11 turns the reached sets into different certificates that a reader can inspect directly. For now keep the logical direction straight: a successful search disproves that the matching is maximum; a complete unsuccessful search proves it, through Berge.

A problem that looks different

A mosaic has some missing squares. Each domino must cover two remaining squares sharing a side, and dominoes may not overlap. A partially tiled mosaic has no place to put one more domino without moving anything. Must it already use the largest possible number of dominoes? What kind of local rearrangement would provide convincing evidence that it does not? The question is left open here: decide what the vertices and edges should represent.

Practise

The browser lab uses separate instances. You draw a search forest from your own code, verify its invariant at each discovery, and read whole components of a comparison certificate. Then you assemble a proof, diagnose an unjustified step, and construct evidence against it. The final story asks for a computed answer and a written proof checked against explicit criteria.

Recap

• You can now: distinguish maximal, maximum and perfect matchings; prove the flip and structure lemmas; prove both directions of Berge including its endpoint argument; and justify the complete directed alternating search in bipartite graphs.
• Invariant: each search parent path alternates from a free left root; flipping a path with two free endpoints preserves the matching and increases its size by one.
• Complexity achieved: one bipartite search costs $O(n+m)$ expected time in the adjacency-list hash model; repeated augmentation costs $O((k+1)(n+m))$ with $k=min(|X|,|Y|)$, compared with enumerating $2^m$ edge subsets.
• Failure mode: confusing no addable edge with no augmenting path, or treating an endpoint of a subpath as free in the whole matching.
• In real software: NetworkX’s hopcroft_karp_matching returns a maximum-cardinality matching of a bipartite graph as a dictionary of partners.
• Retrieval: module 03's bipartition makes path parity visible: every step switches sides. Why must the ends of an odd-length path be on opposite sides?

Check yourself

1. In the sensor graph, which assertion certifies maximality of $\{pr,ts\}$, and which object disproves that it is maximum?
2. Where does Berge's proof use that its surplus path is a whole component, and what contradiction occurs if an endpoint matching edge is shared with the larger matching?
3. Why must a failed bipartite search start from every free vertex of $X$, and why does the proof of Berge itself require no bipartition?

Topic list modeled on the public syllabus of UIUC Math 412 (Graph Theory), which follows D. B. West, Introduction to Graph Theory, 2nd ed., Chapters 1–7. All lessons, proofs, examples, code and exercises here are original. This course is independent and not affiliated with or endorsed by the University of Illinois.