Proof of Vertex Menger by Vertex Splitting

The Vertex Version of Menger’s Theorem

To count internally vertex-disjoint paths between two terminals, the important constraint is how often a path can use an internal vertex. Vertex splitting turns that constraint into a capacity of one. The resulting directed network lets an augmenting-path argument identify a maximum path packing; a separate cut argument then translates the network certificate back into a vertex separator.

The nonadjacency hypothesis matters: a direct edge \(st\) cannot be blocked by deleting an allowed separator vertex. The theorem here is restricted to nonadjacent terminals.

From Vertices to Capacities

Construct a directed network from \(G\). Leave \(s\) and \(t\) unsplit. For each other vertex \(v\), make two nodes \(v^-\) and \(v^+\), and add an arc \(v^-\to v^+\) of capacity \(1\). For each undirected edge \(uv\in E(G)\), add the two directed arcs from the outgoing copy of \(u\) to the incoming copy of \(v\), and from the outgoing copy of \(v\) to the incoming copy of \(u\). For a terminal, its incoming and outgoing copies both mean that terminal. Give each of these edge arcs capacity \(M=n\), where \(n=|V(G)|\). The source is \(s\), and the sink is \(t\).

The split arc \(v^-\to v^+\) is the only way through an internal vertex \(v\). Its unit capacity limits the total flow through that vertex to one. The large edge-arc capacity ensures that a minimum cut of size at most \(n-2\) cannot use an edge arc as one of its cut arcs.

For an integral flow, the residual network records possible changes: an arc with unused capacity \(c-f\) permits additional flow forward, and an arc carrying flow \(f\) permits up to \(f\) units to be sent backward, cancelling that flow. Residual arcs are kept associated with their original arcs, including when the original network has arcs in both directions.

Why Augmenting Paths Give a Minimum Cut

Proof. Initially the flow is integral. Each augmentation adds an integer amount, since all residual capacities are integers, so every flow produced remains integral and feasible. Each augmentation increases the flow value by at least one. The value is bounded above by the sum of capacities on arcs leaving the source, so only finitely many augmentations can occur.

When the process stops, let \(S\) be the nodes reachable from the source in the residual network. The sink is not in \(S\), since otherwise a residual source-to-sink path would allow another augmentation. Every original arc from \(S\) to its complement is saturated: if one had unused capacity, its forward residual arc would make its endpoint reachable. Every original arc from the complement into \(S\) carries zero flow: if it carried positive flow, its backward residual arc would make its tail reachable from its head in \(S\).

Summing flow conservation over nodes in \(S\) shows that the flow value is the flow across the cut in the outward direction minus the flow across it in the inward direction. The outward arcs are saturated and the inward arcs carry zero, so the flow value equals the capacity of the cut. For any feasible flow and any cut, the same conservation sum shows that the flow value is at most the cut capacity. Thus this flow is maximum and this cut is minimum. \(\square\)

In the split network all capacities are integers, so the lemma supplies an integral maximum flow. Its value counts internally vertex-disjoint paths. To see why, an integral flow can be decomposed into source-to-sink paths carrying positive flow, together with possible directed cycles. One way to find a path is to follow positive-flow arcs from the source: if no sink were reachable, summing conservation over the reachable nodes would contradict the positive flow value. Subtract one unit along a simple such path and repeat; any remaining cycles do not contribute to the value. Each source-to-sink path uses at least one split arc because \(s,t\) are nonadjacent. Since each split arc has capacity \(1\), no two extracted paths can use the same internal vertex.

Conversely, each internally vertex-disjoint family gives a feasible integral flow by sending one unit along the network route corresponding to each path. No split arc is used twice. The edge arcs have capacity \(n\), more than the family size, so they do not obstruct this flow. Therefore the maximum integral flow value equals the maximum number of internally vertex-disjoint paths.

Why Network Cuts Give Vertex Separators

First suppose \(s,t\) are connected. Deleting all \(n-2\) internal vertices separates them, because they are nonadjacent. In the split network this gives a cut of capacity at most \(n-2\): take the nodes reachable from \(s\) after removing all internal split arcs. No edge arc leaves this reachable set, and only removed split arcs can cross the cut. Hence a minimum cut has capacity at most \(n-2\), strictly less than \(M=n\).

Proof. Let \(S\) be a minimum cut in the split network. Its capacity is at most \(n-2\), so no edge arc of capacity \(n\) crosses from \(S\) to its complement. Thus every crossing arc is a split arc. Set \(X=\{v\in V(G)\setminus\{s,t\}:v^-\in S,\ v^+\notin S\}\). Each such arc has capacity \(1\), so \(|X|\) equals the cut capacity. If a path in \(G-X\) joined \(s\) to \(t\), its corresponding route in the split network would start in \(S\) and finish outside \(S\). It would have to cross the cut. It cannot cross a split arc for a vertex outside \(X\), by the definition of \(X\), and it cannot cross an edge arc, since none leaves \(S\). This contradiction shows that \(X\) is a separator.

In the other direction, let \(X\) be any \(s\)-\(t\) separator. In the split network delete the split arcs for vertices in \(X\), and let \(R\) be the nodes reachable from \(s\) in what remains. The sink is not in \(R\): a route from \(s\) to \(t\) would project to a walk in \(G-X\), and deleting repetitions from that walk would give a path there. No remaining arc leaves \(R\), by reachability. Therefore, in the original network, every arc leaving \(R\) is among the deleted split arcs, and the cut capacity is at most \(|X|\). The minimum cut is consequently at most the size of every separator, while the first direction produced a separator of size equal to the minimum cut. The two minima are equal. \(\square\)

The augmenting-path lemma gives equality of maximum flow and minimum cut. The path–flow correspondence identifies the maximum flow with the maximum internally vertex-disjoint path count; the cut–separator lemma identifies the minimum cut with the minimum separator size. Together these prove vertex Menger’s theorem when \(s,t\) are connected. If they are disconnected, there are no \(s\)-\(t\) paths and the empty set is already a separator, so both numbers are zero. This completes the proof in all cases covered by the theorem.

Worked Examples

Common Pitfall and Why the Method Matters

Do not replace vertex capacities with unit edge capacities. For example, let \(V(G)=\{s,t,a,b,x,c,d\}\) and \(E(G)=\{sa,ax,xb,bt,sc,cx,xd,dt\}\). The paths \(s,a,x,b,t\) and \(s,c,x,d,t\) are edge-disjoint, but both use the internal vertex \(x\). Every \(s\)-\(t\) path uses \(x\), so the maximum number of internally vertex-disjoint paths is \(1\), and \(\{x\}\) is a separator of size \(1\). Counting edge-disjoint paths would answer a different question. In the split construction, the unit capacity belongs on \(x^-\to x^+\), which records the constraint the theorem is about.

The proof also shows how the method supplies certificates in both directions: a family of internally disjoint paths certifies a lower bound on the separator size, while a small separator certifies an upper bound on the path count. Vertex splitting makes these certificates meet at the same network cut value.