Questions: Menger's Theorem and Edge/Vertex Connectivity

Question 1

In a graph, you find 4 edge-disjoint paths from s to t. What does Menger's theorem guarantee about the minimum edge cut separating s from t?

• A. The minimum edge cut has at most 4 edges
• B. The minimum edge cut has exactly 4 edges
• C. The minimum edge cut has at least 4 edges
• D. The minimum edge cut has at most 2 edges, since each path accounts for 2 endpoint edges

Answer: (B)

Menger's theorem equates the maximum number of edge-disjoint paths with the minimum edge cut size — these two quantities are always equal. If you've found 4 edge-disjoint paths, you know the maximum is at least 4, so the minimum cut must be at least 4 as well. But Menger's theorem says they are exactly equal: the min cut is exactly 4. The theorem is a min-max result, so the answer is not 'at least' but 'exactly.'

Question 2

A student tries to apply Menger's theorem to both edge-disjoint and vertex-disjoint paths, treating them the same way. What is the critical error?

• A. Edge-disjoint and vertex-disjoint paths give the same number — the two versions of the theorem are equivalent
• B. Vertex-disjoint paths share no edges; edge-disjoint paths share no vertices
• C. Edge-disjoint paths may share internal vertices; internally vertex-disjoint paths may not — these measure different connectivity numbers and require different cut concepts
• D. Menger's theorem only applies to the edge version; the vertex version requires a different theorem entirely

Answer: (C)

This is the key common misconception. Edge-disjoint paths only forbid edge sharing — they can freely share vertices. Internally vertex-disjoint paths forbid sharing any internal (non-endpoint) vertex. A graph can have 5 edge-disjoint paths but only 2 internally vertex-disjoint paths between the same pair, because vertices become bottlenecks that edges don't. The two versions of Menger's theorem measure genuinely different graph-theoretic properties: edge connectivity vs. vertex connectivity.

Question 3

Edge-disjoint paths and internally vertex-disjoint paths between the same pair of vertices can yield different counts in the same graph.

• T. True
• F. False

Answer: True

Yes — edge-disjoint paths only require paths to share no edges, so they can pass through the same intermediate vertices. Internally vertex-disjoint paths cannot share any intermediate vertex. A vertex shared by multiple edge-disjoint paths acts as no bottleneck for edge connectivity but would be a bottleneck for vertex connectivity. The two measures are genuinely distinct, and the common misconception is to confuse them.

Question 4

Menger's theorem applies primarily to weighted networks with edge capacities, since it is essentially a special case of the max-flow min-cut theorem.

• T. True
• F. False

Answer: False

This reverses the relationship. Menger's theorem applies to unweighted graphs; the connection to max-flow is that an unweighted graph can be modeled as a flow network where every edge has unit capacity. Max-flow min-cut then gives Menger's theorem as a consequence. But Menger's theorem itself is a result about unweighted graphs — it doesn't require any notion of capacity beyond 'each edge can carry at most one unit of flow.'

Question 5

Why does the vertex version of Menger's theorem require a vertex-splitting construction, and how does this construction work?

Model answer: The vertex version requires controlling how many paths can share an internal vertex, but standard max-flow controls edge capacity, not vertex capacity. The vertex-splitting trick converts each internal vertex v into two vertices v_in and v_out connected by a single unit-capacity edge. Any path through v must use this bottleneck edge, so edge-disjoint paths in the expanded network correspond exactly to internally vertex-disjoint paths in the original graph. Max-flow min-cut can then be applied to the expanded network.

This is the key insight: vertex constraints don't fit naturally into the edge-flow framework, so we transform the problem. By replacing each vertex with an in–out pair connected by a capacity-1 edge, we encode the constraint 'at most one path through this vertex' as an edge capacity constraint. The vertex cut in the original graph corresponds to the min cut through these bottleneck edges in the expanded graph.