= Solution
{c}
The <vertex separator> version of <Menger's theorem> says that, for distinct nonadjacent <vertices> $x,y$ of a finite <graph>, the maximum number of <internally vertex-disjoint paths> from $x$ to $y$ equals the minimum size of an $x$–$y$ <vertex separator>.
Use the following version of the <max-flow min-cut theorem>: in a finite directed <flow network> with nonnegative <integer> <flow network edge capacities>, the maximum <flow value> equals the minimum <cut capacity>, and a <maximum flow> can be chosen to have <integer> values on every directed <edge>. The last clause is the <integral max-flow theorem>.
Here is the reduction, including the correspondence with <vertex separators>. Put $N=|V(G)|$. Perform <vertex splitting> on each <vertex> $v\ne x,y$, replacing it by $v_{\rm in},v_{\rm out}$ with a directed <edge> $v_{\rm in}\to v_{\rm out}$ of <flow network edge capacity> one. Keep $x$ as the source and $y$ as the sink. For each original undirected <edge> $uv$, put directed <edges> from the output of $u$ to the input of $v$ and from the output of $v$ to the input of $u$, each of <flow network edge capacity> $N$; an unsplit endpoint uses $x$ or $y$ itself.
A family of $p$ <internally vertex-disjoint paths> gives a feasible integral <flow> of value $p$, by sending one unit down each <graph path>. Conversely, decompose an integral <flow> into unit source-to-sink <graph paths> and <directed cycles>, discarding the <directed cycles>. This decomposition can be obtained by following positive-<flow> directed <edges> and subtracting one unit along a source-to-sink <graph path> or a <directed cycle>, repeating until the <flow value> is exhausted. A capacity-one split <edge> can belong to at most one unit <graph path>. The projected <graph paths> in $G$ are therefore <internally vertex-disjoint paths>. Thus the largest number of such <graph paths> equals the maximum <flow value>.
Deleting a <vertex separator> $S$ corresponds to removing its split <edges>, of total <flow network edge capacity> $|S|$. This destroys every source-to-sink <graph path>; taking the source-reachable <vertices> after removal gives a <cut of a flow network> of <cut capacity> at most $|S|$. Thus the minimum <cut capacity> is no greater than the minimum <vertex separator> size.
For the reverse inequality, deleting all $N-2$ internal <vertices> separates $x,y$, because they are nonadjacent. Hence a <minimum cut> has <cut capacity> at most $N-2<N$ and cannot contain a directed <edge> of <flow network edge capacity> $N$. Its outgoing <edges> are therefore split <edges>. Let $S$ be the original <vertices> associated with them. Any $x$–$y$ <graph path> avoiding $S$ would lift to a source-to-sink <graph path> crossing this <cut of a flow network> without using an outgoing <edge>, an impossibility. Hence $S$ is a <vertex separator>, with size exactly the <cut capacity>. The two minima agree, and the <max-flow min-cut theorem> proves <Menger's theorem>.
Back to article page
