Menger's theorem: the finite directed and undirected arc, edge and nonadjacent-vertex forms

For a directed graph, delete arcs entering $s$ and arcs leaving $t$; no directed $s$-$t$ path uses one, so this preserves both the path packing number and the minimum arc-separator size. Give every remaining labelled arc capacity one.

In that unit network, cut arcs are arc separators; conversely, after deleting an arc separator, the vertices reachable from $s$ determine a cut whose outgoing arcs are contained in that separator. Thus minimum cut capacity equals minimum arc-separator size.

For an undirected graph, bidirect every edge, delete the now-irrelevant arcs entering $s$ or leaving $t$, and give the remaining labelled arcs unit capacity; a cut then contains exactly one forward copy of each crossing undirected edge.

Cancel the smaller of the two opposed flow values on every original edge. This preserves feasibility and value, since the preprocessing leaves no opposed pair incident with $s$ or $t$; [L1] and [L2] then give paths which are edge-disjoint after orientations are forgotten, proving clause 2.

For the directed vertex form, first make the same source/sink preprocessing. With $n:=\mathrm{\mid }V\mathrm{\mid }$, replace every internal vertex $v$ by a capacity-one arc $v^{-}\to v^{+}$, and replace each original arc by a transport arc of capacity $n$ from the appropriate source copy to target copy.

Deleting every internal vertex arc gives a cut of capacity $n-2<n$, because no $s\to t$ arc exists. Hence a minimum cut uses no transport arc; its vertex arcs are exactly a vertex separator, while every vertex separator gives such a cut.

By [L1], the split network has an integral maximum flow equal to that separator number. By [L2] its unit source-sink path terms number exactly that flow value, while cycle terms have value zero; capacity one on every $v^{-}\to v^{+}$ prevents two such terms from sharing an internal vertex. Projecting them proves clause 3.

For the undirected vertex form, bidirect first and then apply steps 1.5--1.7; nonadjacency gives no $s\to t$ arc, and projection gives internally vertex-disjoint undirected paths, proving clause 4.

By [L1] and [L2], a maximum unit flow decomposes into as many arc-disjoint source-sink paths as its value, so clause 1 follows from step 1.2.

The unit arc construction proves clause 1, its bidirected cancellation proves clause 2, and the capacity-one vertex-arc construction proves clauses 3 and 4.