Proof of Edge Menger by Augmenting Paths

From Augmenting Paths to Edge Menger

Suppose two vertices $s$ and $t$ are connected through a network. One measure of the network’s resilience is the number of routes from $s$ to $t$ that can be used without sharing an edge. Another is the smallest number of edges whose removal disconnects $s$ from $t$. These quantities are equal: if many edge-disjoint routes exist, many edges must be removed to destroy all of them. The substantive part of the theorem is proving that a packing of maximum size always matches a separating edge cut of minimum size.

We give an augmenting-path proof for a finite simple undirected graph $G=(V,E)$ and distinct vertices $s,t\in V$. A path is a sequence of distinct vertices with consecutive vertices adjacent. A family of $s$-$t$ paths is edge-disjoint if no edge occurs in two paths. An edge set $F\subseteq E$ separates $s$ and $t$ if $s$ and $t$ lie in different components of $G-F$. If they are already disconnected, the empty set separates them.

Theorem (Edge Menger). For distinct vertices $s,t$ in a finite undirected graph, the maximum number of pairwise edge-disjoint $s$-$t$ paths equals the minimum size of an edge set separating $s$ and $t$.

For a set $S\subseteq V$, let $\delta(S)$ denote the set of edges with exactly one endpoint in $S$. If $s\in S$ and $t\notin S$, deleting $\delta(S)$ separates $s$ and $t$. Conversely, for any separating set $F$, let $S$ be the vertices reachable from $s$ in $G-F$. Then $t\notin S$, and every edge in $\delta(S)$ belongs to $F$: an edge from $S$ to $V\setminus S$ not in $F$ would make its other endpoint reachable. Thus minimum separating-set size equals the minimum of $|\delta(S)|$ over sets containing $s$ but not $t$.

Signed Unit Flow and Residual Directions

Choose, once and for all, an arbitrary reference orientation for each undirected edge. It is only a bookkeeping choice. For adjacent vertices $u,v$, write $x_{uv}$ for the signed flow from $u$ to $v$, with $x_{vu}=-x_{uv}$. A unit-capacity edge permits $-1\le x_{uv}\le 1$. An integral flow has $x_{uv}\in\{-1,0,1\}$. Its value is the net flow leaving $s$, $\sum_{v:sv\in E}x_{sv}$; at any vertex other than $s,t$, conservation requires $\sum_{v:uv\in E}x_{uv}=0$.

The residual graph has the same vertices as $G$, but its edges are directed: $u\to v$ is available exactly when $x_{uv}<1$. Thus a zero-flow edge can be used in either direction. If one unit currently flows from $u$ to $v$, then $u\to v$ is unavailable but $v\to u$ is available; using that reverse direction cancels the existing flow. An augmenting path is a directed $s$-$t$ path in this residual graph.

Why augmentation works. For each edge $uv$ traversed as $u\to v$, increase $x_{uv}$ by $1$ and decrease $x_{vu}$ by $1$. Since the edge was residual, $x_{uv}<1$; because the flow is integral, $x_{uv}$ was either $0$ or $-1$, so the update leaves it at most $1$ and at least $-1$. At an internal vertex of the augmenting path, one unit enters and one leaves, so conservation is unchanged. The net flow leaving $s$ increases by $1$, and the net flow entering $t$ increases by $1$. Therefore each augmentation gives another feasible integral flow, with value one greater.

Starting from $x=0$, repeatedly find an augmenting path and update the flow. The process must stop: the value is a nonnegative integer, and it is at most $\deg(s)$, since each term $x_{sv}$ is at most $1$. A stopped process has no residual $s$-$t$ path. The next sections show why its value is exactly the desired path-packing and cut size.

Worked Example: A Single Route

Let $V=\{s,a,b,t\}$ and $E=\{sa,ab,bt\}$. There is one evident $s$-$t$ path, but the augmentation also certifies that no second edge-disjoint path is available.

Initially $x=0$, so all three edges are residual in both directions. Augment along $s\to a\to b\to t$. The updated signed values are $x_{sa}=1$, $x_{ab}=1$, and $x_{bt}=1$, where each sign is in the direction displayed. The flow value is $1$. The only residual directions on these edges are now $a\to s$, $b\to a$, and $t\to b$, so there is no residual path from $s$ to $t$.

Check: The path $s,a,b,t$ gives a packing of size $1$. Removing the single edge $ab$ separates $s$ and $t$, so a packing larger than $1$ is impossible, and a separating set of size $1$ exists. The packing and cut sizes agree.

Why a Maximum Integral Flow Gives Paths

A flow is not itself a list of paths: it might contain directed cycles in its positive-flow edges. We need the following fact to turn the final flow into an edge-disjoint path family.

Lemma. If an integral unit-capacity flow has value $k\ge 0$, then its positive-flow edges contain $k$ pairwise edge-disjoint directed $s$-$t$ paths, where each edge is directed in the direction of its positive flow.

Proof. Consider the directed graph consisting of edges $u\to v$ with $x_{uv}=1$. If its flow value is positive, there must be a directed $s$-$t$ path. To prove this, suppose there is none and let $R$ be the vertices reachable from $s$ using positive-flow edges. Then $s\in R$, $t\notin R$, and no positive-flow edge leaves $R$. Sum the net outward flow over vertices in $R$. Contributions from edges internal to $R$ cancel in pairs, leaving the net flow across $\delta(R)$. That net flow is at most $0$, because no positive-flow edge leaves $R$. But conservation makes the sum equal to $k>0$: $s$ contributes $k$, and every other vertex of $R$ has zero net flow, since $t\notin R$. This contradiction proves that a directed path exists.

Choose a simple directed $s$-$t$ path among the positive-flow edges and subtract one unit of flow along it. This preserves conservation at internal vertices, keeps all edge values integral and within their unit bounds, and reduces the flow value by $1$. Repeat while the value is positive. The argument just given applies at each stage with the current positive value, so it produces $k$ paths. No edge can occur in two of them: after its unit of positive flow is used, that edge no longer has positive flow in that direction. The paths are therefore pairwise edge-disjoint. $\square$

In the lemma, edges are oriented in the direction in which the signed flow is positive; this need not be their arbitrary reference orientation. The paths need not use every positive-flow edge: any leftover edges can form directed cycles, which do not affect the conclusion.

Worked Example: Rerouting with a Reverse Residual Edge

Let $V=\{s,a,b,c,d,t\}$ and $E=\{sa,sb,ac,ad,bc,ct,dt\}$. The two edge-disjoint paths $s,a,d,t$ and $s,b,c,t$ will be found even if the first augmentation makes a poor initial choice.

Initially all edges have flow $0$. First choose the augmenting path $s\to a\to c\to t$. Its three edges now carry one unit in the displayed directions, so the flow value is $1$. In particular, the edge $ac$ has flow $a\to c$; its reverse direction $c\to a$ is residual.

The next augmenting path is $s\to b\to c\to a\to d\to t$. The step $c\to a$ cancels the previous unit on $ac$. After this augmentation the nonzero signed flows are $s\to a$, $s\to b$, $b\to c$, $c\to t$, $a\to d$, and $d\to t$, each of value $1$; the net flow on $ac$ is $0$. The value is now $2$.

Reading the positive-flow paths gives $s,a,d,t$ and $s,b,c,t$. They share no edge. For an independent upper bound, the cut $\delta(\{s\})=\{sa,sb\}$ has size $2$, so every edge-disjoint path family has size at most $2$. Thus the packing is maximum and this cut is minimum.

Check: Each displayed path has three edges, and their edge sets $\{sa,ad,dt\}$ and $\{sb,bc,ct\}$ are disjoint. Both use edges of $G$, so they verify a packing of size $2$; the two-edge cut at $s$ verifies the matching upper bound.

The Terminal Residual Set Produces a Minimum Cut

Run augmentations until no residual $s$-$t$ path remains. Let $S$ be the set of vertices reachable from $s$ in the final residual graph. Then $s\in S$ and $t\notin S$. If $u\in S$, $v\notin S$, and $uv\in E$, the direction $u\to v$ cannot be residual; otherwise $v$ would also be reachable. Consequently $x_{uv}=1$, because $x_{uv}$ is an integer at most $1$ and residual availability is exactly $x_{uv}<1$. Every edge in $\delta(S)$ therefore carries one unit outward from $S$.

Cut identity. At any feasible flow with $s\in S$ and $t\notin S$, the net flow outward across $\delta(S)$ equals the flow value. Indeed, when the net outward flow is summed over all vertices in $S$, flows on edges internal to $S$ cancel. Conservation makes every vertex in $S$ other than $s$ contribute zero, while $s$ contributes the flow value. For the terminal residual set, every crossing edge carries one unit outward, so this identity gives $$ \text{flow value}=|\delta(S)|. $$

Worked Example: No Route Between the Terminals

Let $V=\{s,a,b,t\}$ and $E=\{sa,ab\}$. The vertices $s$ and $t$ are distinct, but $t$ is isolated. Initially the flow is zero. There is no residual $s$-$t$ path, so the algorithm stops without augmentation and the flow value is $0$.

The residual vertices reachable from $s$ are $S=\{s,a,b\}$: the edges $sa$ and $ab$ are available in both directions at zero flow. The complement is $\{t\}$, and $\delta(S)=\varnothing$, so its size is $0$.

Check: There are no $s$-$t$ paths, hence the maximum packing size is $0$. Deleting the empty edge set already leaves $s$ and $t$ disconnected, so the minimum separating-set size is also $0$. This covers the disconnected case without requiring a positive augmentation.

Proof of Edge Menger’s theorem. Start with zero flow and augment until no residual $s$-$t$ path remains. The process terminates because each augmentation raises the integer flow value by $1$, while that value is at most $\deg(s)$. Let the final value be $k$, and let $S$ be the final residual set of vertices reachable from $s$. The cut identity gives $|\delta(S)|=k$. The integral-flow lemma gives $k$ pairwise edge-disjoint $s$-$t$ paths.

It remains to show that no packing can be larger and no separating set can be smaller. Every $s$-$t$ path crosses $\delta(S)$, since it starts in $S$ and ends outside $S$. In an edge-disjoint family, different paths must cross on different edges, so any such family has size at most $|\delta(S)|=k$. Also, if $F$ is any edge set separating $s$ and $t$, every $s$-$t$ path must use an edge of $F$; edge-disjoint paths must use distinct such edges. Thus $k$ paths imply $|F|\ge k$. We have exhibited both a packing and a separating cut of size $k$, so the maximum packing size and minimum separating-set size are equal. $\square$

A Common Mistake and the Main Idea

A common mistake is to forbid using an edge backwards once it has been used. In the rerouting example, after sending one unit along $s,a,c,t$, treating $ac$ as permanently unavailable would conceal the second augmentation. The residual direction $c\to a$ is not an extra unit of capacity: it cancels the existing unit on $ac$. After cancellation, the flow uses $a\to d$ and $b\to c$, giving the two edge-disjoint paths found above.

The proof has two complementary certificates. A collection of $k$ edge-disjoint paths shows that at least $k$ edges must be removed to separate the terminals. A terminal residual set produces a cut of exactly $k$ edges. The augmenting argument is what ensures that these two certificates can be made to match.

Check Your Understanding

Use the signed-flow and cut arguments to answer the following.

Why is $u\to v$ residual when $x_{uv}=0$, and why is $v\to u$ residual when $x_{uv}=1$?
Explain why augmenting along a residual path preserves conservation at each internal vertex.
For $V=\{s,a,t\}$ and $E=\{sa,at,st\}$, give two edge-disjoint $s$-$t$ paths and a separating cut of size $2$.
In the integral-flow lemma, why can no edge occur in two of the paths produced by successive subtractions?
Why does the terminal residual set have no residual edge directed from $S$ to $V\setminus S$?