The Edge Version of Menger's Theorem

Two Ways to Measure Connection

Suppose two vertices communicate through a network. One way to assess the strength of their connection is to count how many separate routes can be used without sharing an edge. Another is to ask how many edges must fail before the vertices become disconnected. Edge Menger’s theorem says that these two quantities are equal. The statement is local: it concerns a specified pair of vertices, not the connectivity of the whole graph.

All graphs in this tutorial are finite and simple. A path has no repeated vertices. Two paths are edge-disjoint if they have no edge in common; they may share vertices, including internal vertices. For distinct vertices \(u,v\), an edge cut separating \(u\) from \(v\) is a set \(F\subseteq E(G)\) such that \(u\) and \(v\) lie in different connected components of \(G-F\). Here \(G-F\) is obtained by deleting the edges in \(F\), while retaining all vertices.

These maxima and minima exist: the graph is finite, so there are finitely many paths and edge sets to consider. The empty family of paths is allowed; it is the only possible size of a family when \(u\) and \(v\) are disconnected.

The Edge Version of Menger’s Theorem

In words, the largest number of pairwise edge-disjoint \(u\)-\(v\) paths equals the fewest edges whose deletion separates \(u\) from \(v\). The theorem also covers the disconnected case: both quantities are zero.

We prove the theorem using the integral max-flow/min-cut theorem. We state the required standard result precisely; its proof belongs to the theory of network flows and is not given here.

A flow assigns a value to each directed arc, between zero and its capacity, so that at every vertex other than the source and sink the total inflow equals the total outflow. Its value is the net outflow from the source. A source-sink cut is a partition of the vertices into sets \(S\) and \(\overline S\), with the source in \(S\) and the sink in \(\overline S\); its capacity is the sum of capacities of arcs directed from \(S\) to \(\overline S\).

Proof. Fix distinct \(u,v\in V(G)\). Form a directed network by replacing each undirected edge \(xy\in E(G)\) with two directed arcs, \(x\to y\) and \(y\to x\), each of capacity \(1\). Take \(u\) as source and \(v\) as sink.

First compare the minimum cut capacity in this network with \(\lambda'_G(u,v)\). For any vertex set \(S\) with \(u\in S\) and \(v\notin S\), exactly one of the two arcs associated with each edge having one endpoint in \(S\) and one outside \(S\) is directed out of \(S\). Thus the cut capacity is exactly the number of such edges. Deleting all these edges separates \(u\) from \(v\), so every such cut gives an edge cut of the same size.

Conversely, let \(F\) be any edge cut separating \(u\) from \(v\), and let \(S\) be the set of vertices reachable from \(u\) in \(G-F\). Then \(u\in S\) and \(v\notin S\). Every edge of \(G\) with one endpoint in \(S\) and one outside \(S\) must belong to \(F\); otherwise that edge would make its outside endpoint reachable. Therefore the cut determined by \(S\) has size at most \(|F|\). Taking minima in both directions shows that the minimum network cut capacity is \(\lambda'_G(u,v)\).

By the integral max-flow/min-cut theorem, there is an integer-valued maximum flow whose value is \(\lambda'_G(u,v)\). If this flow sends positive amounts in both directions along the arcs associated with some edge \(xy\), subtract the smaller of those two amounts from both arcs. This preserves flow conservation and the net flow value. Repeating this for each edge gives an integer maximum flow with no edge carrying positive flow in both directions. Since each arc has capacity \(1\), every positive arc now carries exactly \(1\).

We next extract paths from this flow. Whenever the remaining flow has positive value, there is a directed \(u\)-\(v\) path consisting of positive-flow arcs. Indeed, if \(v\) were not reachable from \(u\) along such arcs, let \(R\) be the set reachable from \(u\). No positive-flow arc leaves \(R\), while \(v\notin R\). Summing flow conservation over the vertices of \(R\) says that the net flow leaving \(R\) is the flow value, which is positive. But with no positive-flow arc leaving \(R\), that net flow cannot be positive. This contradiction proves that a positive-flow path exists. Removing loops from a directed walk gives a path with no repeated vertices.

Subtract one unit of flow from the arcs of this path. The remaining flow is still nonnegative and integral, conservation still holds at every internal vertex, and the value decreases by one. Repeating this operation produces as many \(u\)-\(v\) paths as the original flow value. No two extracted paths use the same directed arc, because each such arc initially carried at most one unit. Nor can two paths use the same undirected edge in opposite directions, because the flow was normalized to have no positive flow in both directions along an edge. Thus the paths are pairwise edge-disjoint. This proves \(\lambda_G(u,v)\ge\lambda'_G(u,v)\).

For the reverse inequality, take any edge cut \(F\) separating \(u\) from \(v\). Every \(u\)-\(v\) path must use at least one edge of \(F\); otherwise that path would remain in \(G-F\). In a family of edge-disjoint paths, different paths must use different edges of \(F\). Hence every such family has size at most \(|F|\). Taking the minimum over separating edge cuts gives \(\lambda_G(u,v)\le\lambda'_G(u,v)\). The two inequalities prove the theorem. \(\square\)

Reading the Two Certificates

A collection of edge-disjoint paths is a certificate for a lower bound on \(\lambda_G(u,v)\): it proves that at least that many paths exist. A separating edge cut is a certificate for an upper bound: no edge-disjoint path family can be larger than the cut. When the two certificates have the same size, the theorem confirms that both quantities have been determined exactly.

Common Pitfall: Vertices May Be Shared

Edge-disjoint does not mean internally vertex-disjoint. For example, in the graph with \(V=\{s,x,t\}\) and \(E=\{sx,xt\}\), there are not two edge-disjoint \(s\)-\(t\) paths: there is only the path \(s,x,t\), and both edges are required. The minimum separating edge cut has size \(1\), since deleting \(sx\) separates \(s\) from \(t\).

A tempting but incorrect calculation is to count the two edges incident with \(x\) and conclude that there are two edge-disjoint paths. Those edges are not two complete \(s\)-\(t\) routes; every such route must use both. The correction is to identify full paths and check that no edge is repeated, then compare their number with an actual separating cut. The theorem concerns edges throughout, not the number of incident edges at an internal vertex.

In applications, the equality gives two complementary ways to reason about resilience. Exhibiting several edge-disjoint routes proves that the network tolerates the loss of fewer edges without disconnecting the chosen pair. Exhibiting a small separating cut identifies a specific vulnerability. The theorem guarantees that exact path and cut certificates can always be matched in size.