Editing Menger's theorem (section)

==Short proof==
Most direct proofs consider a more general statement to allow proving it by induction. It is also convenient to use definitions that include some degenerate cases.
The following proof for undirected graphs works without change for directed graphs or multi-graphs, provided we take ''path'' to mean directed path.

For sets of vertices ''A,B ⊂ G'' (not necessarily disjoint), an ''AB-path'' is a path in ''G'' with a starting vertex in ''A'', a final vertex in ''B'', and no internal vertices either in ''A'' or in ''B''. We allow a path with a single vertex in ''A ∩ B'' and zero edges.
An ''AB-separator'' of size ''k'' is a set ''S'' of ''k'' vertices (which may intersect ''A'' and ''B'') such that ''G−S'' contains no ''AB''-path.
An ''AB-connector'' of size ''k'' is a union of ''k'' vertex-disjoint ''AB''-paths.

: '''Theorem:''' The minimum size of an ''AB''-separator is equal to the maximum size of an ''AB''-connector.

In other words, if no ''k''−1 vertices disconnect ''A'' from ''B'', then there exist ''k'' disjoint paths from ''A'' to ''B''.
This variant implies the above vertex-connectivity statement: for ''x,y ∈ G'' in the previous section, apply the current theorem to ''G''−{''x,y''} with ''A = N(x)'', ''B = N(y)'', the neighboring vertices of ''x,y''.  Then a set of vertices disconnecting ''x'' and ''y'' is the same thing as an
''AB''-separator, and removing the end vertices in a set of independent ''xy''-paths gives an ''AB''-connector.

''Proof of the Theorem:''<ref>{{cite journal |doi=10.1016/S0012-365X(00)00088-1 |title=Short proof of Menger's theorem |journal=Discrete Mathematics |volume=219 |issue=1–3 |pages=295–296 |year=2000 |last1=Göring |first1=Frank |doi-access=free }}</ref>
Induction on the number of edges in ''G''.
For ''G'' with no edges, the minimum ''AB''-separator is ''A ∩ B'',
which is itself an ''AB''-connector consisting of single-vertex paths.

For ''G'' having an edge ''e'', we may assume by induction that the Theorem holds for ''G−e''. If ''G−e'' has a minimal ''AB''-separator of size ''k'', then there is an ''AB''-connector of size ''k'' in ''G−e'', and hence in ''G''.

[[File:Proof of Menger's Theorem.svg|thumb|An illustration for the proof.]]

Otherwise, let ''S'' be a ''AB''-separator of ''G−e'' of size less than ''k'',
so that every ''AB''-path in ''G'' contains a vertex of ''S'' or the edge ''e''.
The size of ''S'' must be ''k-1'', since if it was less, ''S'' together with either endpoint of ''e'' would be a better ''AB''-separator of ''G''.
In ''G−S'' there is an ''AB''-path through ''e'', since ''S'' alone is too small to be an ''AB''-separator of ''G''.
Let ''v<sub>1</sub>'' be the earlier and ''v<sub>2</sub>'' be the later vertex of ''e'' on such a path.
Then ''v<sub>1</sub>'' is reachable from ''A'' but not from ''B'' in ''G−S−e'', while ''v<sub>2</sub>'' is reachable from ''B'' but not from ''A''.

Now, let ''S<sub>1</sub> = S ∪ {v<sub>1</sub>}'', and consider a minimum ''AS<sub>1</sub>''-separator ''T'' in ''G−e''.
Since ''v<sub>2</sub>'' is not reachable from ''A'' in ''G−S<sub>1</sub>'', ''T'' is also an ''AS<sub>1</sub>''-separator in ''G''.
Then ''T'' is also an ''AB''-separator in ''G'' (because every ''AB''-path intersects ''S<sub>1</sub>'').
Hence it has size at least ''k''.
By induction, ''G−e'' contains an ''AS<sub>1</sub>''-connector ''C<sub>1</sub>'' of size ''k''.
Because of its size, the endpoints of the paths in it must be exactly ''S<sub>1</sub>''.

Similarly, letting ''S<sub>2</sub> = S  ∪ {v<sub>2</sub>}'', a minimum ''S<sub>2</sub>B''-separator has size ''k'', and there is 
an ''S<sub>2</sub>B''-connector ''C<sub>2</sub>'' of size ''k'', with paths whose starting points are exactly ''S<sub>2</sub>''.

Furthermore, since ''S<sub>1</sub>'' disconnects ''G'', every path in ''C<sub>1</sub>'' is internally disjoint from 
every path in ''C<sub>2</sub>'', and we can define an ''AB''-connector of size ''k'' in ''G'' by concatenating paths (''k−1'' paths through ''S'' and one path going through ''e=v<sub>1</sub>v<sub>2</sub>''). Q.E.D.