Questions: Menger's Theorem and Network Connectivity

Question 1

A communications network has exactly 3 edge-disjoint paths between server A and server B. According to Menger's theorem, what can be concluded about the minimum number of edges whose removal disconnects A from B?

• A. At least 3 edges must be removed, but possibly more
• B. Exactly 3 edges must be removed — the maximum number of edge-disjoint paths equals the minimum edge cut
• C. It depends on the rest of the network topology
• D. The minimum cut could be as low as 1 if a single edge appears in all paths

Answer: (B)

Menger's theorem establishes an equality: max edge-disjoint paths = min edge cut. If you can find 3 edge-disjoint paths, you know the minimum cut is exactly 3. This is not just a lower bound — it's exact. Option A describes only the easy half (any cut must sever all disjoint paths, so the cut size ≥ the number of disjoint paths); Menger's theorem gives you the other direction too.

Question 2

To prove the vertex form of Menger's theorem using the edge form, each internal vertex v is replaced by:

• A. Two vertices v_in and v_out connected by a single edge of capacity 1, forcing every path through v to use that edge
• B. Two vertices with an edge of unlimited capacity, preserving the graph structure
• C. An edge connecting all of v's neighbors directly to each other
• D. A copy of v connected to an auxiliary sink vertex

Answer: (A)

The 'splitting' construction converts vertex capacity into edge capacity: replacing v with v_in → v_out (capacity 1 edge) means any path through v must use that edge, using up one unit of capacity. Once each vertex is split this way, every vertex-disjoint path in the original graph corresponds to an edge-disjoint path in the split graph, and vice versa. The edge form of Menger's theorem then applies directly.

Question 3

In Menger's theorem, edge-disjoint paths between u and v may share intermediate vertices.

• T. True
• F. False

Answer: True

Edge-disjoint means no edge appears in more than one path — but intermediate vertices can be shared. This contrasts with vertex-disjoint paths, which share no intermediate vertex. The distinction matters because there are two forms of Menger's theorem: the edge form (max edge-disjoint paths = min edge cut) and the vertex form (max vertex-disjoint paths = min vertex cut). Confusing the two leads to misapplying the theorem.

Question 4

Menger's theorem is a surprising result because it is not obvious in advance that the maximum number of edge-disjoint paths and the minimum edge cut would be equal rather than just related by an inequality.

• T. True
• F. False

Answer: True

The easy direction is clear: any cut must sever every disjoint path, so min cut ≥ max disjoint paths. But the theorem gives equality — the cut never needs to be larger than the number of disjoint paths you can find. This is the non-obvious direction, and it requires proof (via max-flow min-cut). Many combinatorial min-max equalities have this structure: Hall's theorem, König's theorem, and Dilworth's theorem are other examples where equality, not merely inequality, holds.

Question 5

Why is Menger's theorem considered a consequence of the max-flow min-cut theorem, and what translation is required?

Model answer: To translate Menger's theorem into a flow problem, assign capacity 1 to every edge. An integer max-flow of value k from u to v decomposes into k edge-disjoint unit flows, each tracing an edge-disjoint path. A minimum cut of capacity k corresponds to k edges whose removal disconnects u from v. Max-flow min-cut then gives max-paths = min-cut directly. The key insight is that capacity-1 networks force integer solutions, so flow values correspond exactly to path counts.

This reduction is a general template in combinatorial optimization: to prove a combinatorial min-max equality, translate it into a flow problem and apply max-flow min-cut. The same technique works for bipartite matching (via capacity-1 bipartite networks), Hall's theorem, and many other structural results. Menger's theorem is thus not an isolated result but an instance of a broader duality principle.