Motivation
A route is robust when the network offers alternatives that do not fail together. But the resource that may fail matters. Two paths can use different edges while sharing one crucial intermediate vertex. Removing an edge and removing a vertex are therefore different obstruction problems, even for the same two endpoints.
Menger's theorems identify the largest collection of independent routes with the smallest obstruction destroying every route. A family of disjoint paths gives one side of an optimality certificate; a separator gives the other. We will derive both equalities from the integral max-flow min-cut theorem already proved in the residual-network chapter, explaining the additional modeling steps rather than hiding them inside the phrase “reduce to flow.”
Definitions
Definition 9.2.1
(Disjoint paths and separators)
Let be a finite simple undirected graph and let be distinct vertices. All paths here are simple. Paths are edge-disjoint when they share no edge; they may share vertices. They are internally vertex-disjoint when their only common vertices are the endpoints . An edge separator is a set of edges whose deletion leaves no – path. An internal vertex separator is a subset of whose deletion leaves no such path.
If the endpoints are already disconnected, the empty separator is permitted and there are zero routes to pack. The internal vertex theorem will assume that the endpoints are nonadjacent. If an edge directly joins them, deleting internal vertices can never destroy that edge, so the specified separator problem has no finite solution.
For a vertex set containing but not , let be the set of undirected edges with one endpoint in and the other outside. Such a boundary is an edge separator. Conversely, after deleting any edge separator, take the vertices reachable from ; every edge in their boundary must have been deleted. Thus the smallest separator size equals the smallest boundary size.
Theorem/Proposition
Theorem 9.2.2
(Edge form of finite undirected Menger)
The maximum number of pairwise edge-disjoint – paths equals the minimum size of an edge separator. Equivalently, it equals . This statement applies whether or not are adjacent.
Theorem 9.2.3
(Internal vertex form of finite undirected Menger)
If are distinct nonadjacent vertices, the maximum number of internally vertex-disjoint – paths equals the minimum size of an internal vertex separator. Endpoints are never deleted and are not counted as internal vertices.
Any separator must meet every packed path. For disjoint paths, its individual deleted resources must be distinct. This gives the easy inequality in both theorems. The substance is the converse: an obstruction of minimum size can always be matched by that many compatible routes.
Proof sketch or proof idea
We use the following already established flow result. A finite directed network with nonnegative integer capacities has an integral maximum flow, and its value equals the minimum cut capacity. Arcs entering the source or leaving the sink are allowed; flow value means net outgoing source flow. This precise formulation is useful when replacing undirected edges by opposite arcs.
Routes are extracted from flows by the following lemma.
Lemma 9.2.4
(Integral flows decompose into paths)
Let be a nonnegative integral flow of value from a source to a sink in a finite directed network. Then there are simple directed – paths , repetitions allowed, such that every arc lies on at most of them.
Proof
(Proof by repeatedly removing a positive-flow path)
If the value is positive, there is a positive-flow directed path from source to sink. Otherwise let be the vertices reachable from the source through positive-flow arcs. No positive flow leaves , so its net outward flow is nonpositive. Conservation and exclusion of the sink instead make that net flow the positive source value, a contradiction. Choose a simple positive-flow path and subtract its smallest positive arc flow. This preserves conservation and lowers the value by a positive integer. Repeating extracts paths carrying the whole value; a remaining circulation of value zero can be discarded. A path carrying several units is listed with that multiplicity. Since every subtraction keeps the flow nonnegative, the listed paths use each arc at most times.
Proof
(Proof of the edge form)
Replace every undirected edge by arcs and , each of capacity one. A directed cut has exactly one outward arc for each undirected boundary edge, so the minimum cut capacity equals the minimum edge-separator size. Choose an integral maximum flow.
Opposite arcs might both carry one unit. Cancel the smaller of their two flows from both. At each endpoint, the same amount is removed from incoming and outgoing flow, so conservation and net value are unchanged. After all cancellations, at most one orientation of each original edge carries positive flow. Decompose this flow into paths. Since arc capacities are one, extracted paths use distinct arcs; because opposite positive orientations were removed, they also use distinct undirected edges. Conversely, orienting any family of edge-disjoint paths from toward gives a feasible flow of that value. The maximum flow and minimum cut now prove the equality.
Proof
(Proof of the internal vertex form)
Write and use a directed split network. Keep unsplit. Replace each other vertex by , joined by a directed arc of capacity one. For every undirected edge, add both corresponding directions from the output copy of one endpoint to the input copy of the other, each of capacity . For unsplit endpoints, their input and output copies both mean the original endpoint.
An integral flow decomposes into paths, and every visit to an internal original vertex must cross its capacity-one split arc. Thus extracted routes are internally vertex-disjoint. Conversely, such a path family gives an integral flow; its size is at most , since each route uses at least one internal vertex when the endpoints are nonadjacent. The capacity is large enough for every adjacency arc.
Deleting all split arcs disconnects the source from the sink. Taking a reachable-set cut after that deletion gives a cut of capacity at most . Hence a minimum cut cannot contain an outward adjacency arc of capacity . Its outward arcs are therefore only split arcs. Let be their original vertices. The cut capacity is , and any original path avoiding would lift to a network path crossing none of the cut arcs, which is impossible. Thus is an internal vertex separator. Maximum integral flow supplies the same number of disjoint routes, completing the proof.
Proof X-ray
Separate capacity limits from certificate extraction
The vertex proof has three working parts. First, the unit capacity on each split arc is the only place where disjointness is enforced.
Second, the decisive move is the capacity on adjacency arcs. It is used only when a minimum cut is decoded: the split arcs alone already give a cut of capacity at most , so no minimum cut can afford an adjacency arc. Its outward arcs are split arcs and name a vertex set whose size is the cut capacity.
Third, the nonadjacency hypothesis enters at exactly that point. If , the arc survives the deletion of all split arcs, the bound is unavailable, and every cut must pay for that arc. The integral max-flow min-cut equality then closes the proof through the two translations, flow to routes and cut to separator.
Worked examples
Worked example 9.2.5
(Two edge routes share one vulnerable vertex)
Take paths and , with exactly their eight edges. They share no edge, so two edge-disjoint routes exist. The two edges incident to form an edge separator, proving the edge optimum is two. Every route passes through , however, so is an internal vertex separator. There is a route, so the vertex optimum is exactly one. Edge independence did not imply vertex independence.
Worked example 9.2.6
(Three independent intermediate choices)
Join each of to both and , with no edge . The three paths through the separate intermediate vertices are internally vertex-disjoint. Deleting all three intermediates separates the endpoints, while deleting only two leaves one route. In the split network there are three capacity-one internal arcs and adjacency capacity . Maximum flow and minimum cut both have value three. The source and sink are shared by all three paths, as the theorem permits.
Worked example 9.2.7
(Path length is not the packing objective)
Take the five-cycle . It supplies routes and of lengths three and two. They are internally vertex-disjoint as well as edge-disjoint. The boundary at has two edges, and deleting internal neighbors isolates . Both local separator optima are therefore two. A maximum collection need not consist of equally short paths, nor does the theorem minimize their total length.
Why cancellation precedes edge decomposition
A directed flow counts directed arcs as separate resources. In the undirected model, traveling an edge in one direction and traveling it in the other still use the same underlying edge. Decomposing before addressing that distinction could produce paths that are disjoint as directed arc lists but violate the desired undirected requirement.
Cancellation fixes the model without changing the objective. It removes a two-arc circulation, not useful net transport. Once only one positive orientation remains, subsequent decomposition only subtracts flow and never creates a new opposite direction. The extracted paths therefore stay edge-disjoint in the original graph. This is a correctness step, not merely a tidier way to display the routes.
Internally disjoint means endpoints are reusable
Splitting every vertex with unit capacity, including the source, would limit the entire answer to one. The endpoints are deliberately exempt because each packed route must use them. Similarly, an internal separator excludes the endpoints: otherwise deleting the source would trivialize every connected instance.
The nonadjacency hypothesis makes the minimum-separator statement meaningful under that convention. It also supplies a finite upper bound for choosing the large capacity in the reduction: all internal vertices together are a valid separator. If a direct endpoint edge is present, this set does not separate them, and the proof's small-cut argument breaks at exactly the corresponding point.
Counterexample mode
An adjacent pair has no internal-vertex separator
In a triangle with vertices , the paths and are internally vertex-disjoint. Their maximum number is finite, namely two. But no subset of the only internal vertex set destroys the direct edge . Thus the stated separator minimum is unavailable. The repaired vertex theorem assumes nonadjacent endpoints; the edge theorem needs no such restriction.
Local certificates and a global edge-connectivity statement
If every pair has at least edge-disjoint paths, deleting fewer than edges leaves every pair connected. Each deleted edge can disrupt at most one route in a particular disjoint family, so at least one route survives. Conversely, if deletion of fewer than edges always leaves the graph connected, every local edge separator has size at least . Menger then supplies edge-disjoint routes for every pair.
This gives a precise interpretation of finite -edge-connectivity when the graph has at least two vertices. The statement is about all pairs. A single highly connected pair does not certify the whole graph: another vertex can be attached by one bridge while the first pair retains many alternatives.
A simple necessary local bound is the degree of each endpoint. Edge-disjoint routes need distinct first edges, so their number is at most either endpoint degree. For nonadjacent endpoints, internally disjoint routes also need distinct first internal vertices. These bounds are quick obstructions, but they do not prove the corresponding lower bound; a bottleneck farther inside the graph may be smaller.
Greedy path deletion can lose an optimum
Finding one route and permanently deleting all its internal vertices does not automatically construct a largest family. In the graph with edges , choosing removes both internal vertices and leaves no route. Yet and form a family of two. A maximal family can therefore be smaller than a maximum family.
Residual algorithms can revise earlier decisions. A separator discovered when no further residual improvement exists is a mathematical certificate; a failure to find another route after irreversible greedy deletions is not. This distinction parallels maximal versus maximum matching and is a useful warning whenever a packing problem invites a local selection rule.
Common mistakes
Common mistake
(A travel capacity that is too small hides the separator)
In the split network, the adjacency arcs must carry a capacity strictly above a known separator bound, such as above . With capacity one, a minimum cut may consist of travel arcs and name no vertex at all, as for the path .
A path family and separator of equal size certify optimality independently of how they were found. Showing several routes without an upper bound proves only feasibility; showing a small separator without routes proves only an obstruction.
Summary
Integral flows become edge-disjoint routes after opposite-direction cancellation and path decomposition. Split vertices enforce internal disjointness, while large travel capacities let minimum cuts decode into vertex separators. The hypotheses distinguish genuine connectivity equalities from adjacent-endpoint exceptions and greedy failures.
Exercises
Quick check
(Take the graph with edges . Find both local path-packing optima and corresponding separators.)
The source has degree two, but there is only one final edge to the sink.
Solution · Answer
Every – route uses , so the edge packing is at most one; attains one. The single edge is a minimum edge separator. Every route also uses internal vertex , so the internal-vertex packing and separator size are both one, certified by that same route and vertex set . Endpoint degree two alone did not force two routes.
Quick check
(Prove the global equivalence between surviving every deletion of fewer than edges and having edge-disjoint paths between every pair.)
Assume a finite graph with at least two vertices and an integer .
Solution · Answer
If each pair has edge-disjoint routes, a deleted set with fewer than edges cannot meet all routes of any one pair, so the surviving graph is connected. Conversely, if all such deletions preserve connectivity, no pair has an edge separator of size below . The edge theorem therefore gives at least disjoint routes for each pair. The conclusion is simultaneous availability pair by pair, not a demand that all pairs' chosen families be mutually disjoint.
Quick check
(Why may capacity one on every travel arc fail to decode a minimum cut into an internal vertex separator? Use the path .)
A valid flow value and a correctly interpreted cut are separate requirements.
Solution · Answer
With unit travel capacities, the split network for has the cut whose source side is just . It crosses the travel arc into , has capacity one and is minimum. It crosses no internal split arc, so the proposed extracted vertex set would be empty, which does not separate the original path. A travel capacity larger than the known internal-separator bound prevents such a cut from being minimum.