Editing Menger's theorem (section)

== Other proofs ==
The directed edge version of the theorem easily implies the other versions.
To infer the directed graph vertex version, it suffices to split each vertex ''v'' into two vertices ''v<sub>1</sub>'', ''v<sub>2</sub>'', with all ingoing edges going to ''v<sub>1</sub>'', all outgoing edges going from ''v<sub>2</sub>'', and an additional edge from ''v<sub>1</sub>'' to ''v<sub>2</sub>''.
The directed versions of the theorem immediately imply undirected versions: it suffices to replace each edge of an undirected graph with a pair of directed edges (a digon).

The directed edge version in turn follows from its weighted variant, the [[max-flow min-cut theorem]].
Its [[Max-flow min-cut theorem#Proof|proof]]s are often correctness proofs for max flow algorithms.
It is also a special case of the still more general (strong) [[Linear programming#Duality|duality theorem]] for [[linear program]]s.

A formulation that for finite digraphs is equivalent to the above formulation is:
: Let ''A'' and ''B'' be sets of vertices in a finite [[directed graph|digraph]] ''G''. Then there exists a family ''P'' of disjoint ''AB''-paths and an ''AB''-separating set that consists of exactly one vertex from each path in ''P''.

In this version the theorem follows in fairly easily from [[Kőnig's theorem (graph theory)|Kőnig's theorem]]: in a [[bipartite graph]], the minimal size of a cover is equal to the maximal size of a matching.

This is done as follows: replace every vertex ''v'' in the original digraph ''D'' by two vertices ''v' '', ''v<nowiki>''</nowiki>'', and every edge ''uv'' by the edge ''u'v<nowiki>''</nowiki>''; additionally, include the edges ''v'v<nowiki>''</nowiki>'' for every vertex ''v'' that is neither in ''A'' nor ''B''. This results in a bipartite graph, whose one side consists of the vertices ''v' '', and the other of the vertices ''v<nowiki>''</nowiki>''.

Applying Kőnig's theorem we obtain a matching ''M'' and a cover ''C'' of the same size. In particular, exactly one endpoint of each edge of ''M'' is in ''C''. Add to ''C'' all vertices ''a<nowiki>''</nowiki>'', for ''a'' in ''A,'' and all vertices ''b' '', for ''b'' in ''B''. Let ''P'' be the set of all ''AB''-paths composed of edges ''uv'' in ''D'' such that ''u'v<nowiki>''</nowiki>'' belongs to M. Let ''Q'' in the original graph consist of all vertices ''v'' such that both ''v' '' and ''v<nowiki>''</nowiki>'' belong to ''C''. It is straightforward to check that ''Q'' is an ''AB''-separating set, that every path in the family ''P'' contains precisely one vertex from ''Q'', and every vertex in ''Q'' lies on a path from ''P'', as desired.<ref>{{cite journal |doi=10.1016/S0195-6698(83)80012-2 |title=Menger's theorem for graphs containing no infinite paths |journal=European Journal of Combinatorics |volume=4 |issue=3 |pages=201–4 |year=1983 |last1=Aharoni |first1=Ron |doi-access=free }}</ref>