Editing Menger's theorem

{{short description|Theorem in graph theory}}

In the [[mathematical]] discipline of [[graph theory]], '''Menger's theorem''' says that in a [[finite graph]], the size of a minimum [[cut set]] is equal to the maximum number of disjoint paths that can be found between any pair of [[Vertex (graph theory)|vertices]].
Proved by [[Karl Menger]] in 1927, it [[Characterization (mathematics)|characterizes]] the [[connectivity (graph theory)|connectivity]] of a graph.
It is generalized by the [[max-flow min-cut theorem]], which is a weighted, edge version, and which in turn is a special case of the [[Linear programming#Duality|strong duality theorem]] for linear programs.

==Edge connectivity==
The '''edge-connectivity''' version of Menger's theorem is as follows:

:Let ''G'' be a finite undirected graph and ''x'' and ''y'' two distinct vertices. Then the size of the minimum [[Edge cut#Connectivity|edge cut]] for ''x'' and ''y'' (the minimum number of edges whose removal disconnects ''x'' and ''y'') is equal to the maximum number of pairwise [[path (graph theory)#Examples|edge-disjoint path]]s from ''x'' to ''y''.

The implication for the graph ''G'' is the following version:

:A graph is [[K-edge-connected graph|''k''-edge-connected]] (it remains connected after removing fewer than ''k'' edges) if and only if every pair of vertices has ''k'' edge-disjoint paths in between.

==Vertex connectivity==
The '''vertex-connectivity''' statement of Menger's theorem is as follows:

:Let ''G'' be a finite undirected graph and ''x'' and ''y'' two [[nonadjacent]] vertices. Then the size of the minimum [[vertex cut]] for ''x'' and ''y'' (the minimum number of vertices, distinct from ''x'' and ''y'', whose removal disconnects ''x'' and ''y'') is equal to the maximum number of pairwise [[path (graph theory)|internally disjoint paths]] from ''x'' to ''y''.

A consequence for the entire graph ''G'' is this version:

:A graph is [[K-vertex-connected graph|''k''-vertex-connected]] (it has more than ''k'' vertices and it remains connected after removing fewer than ''k'' vertices) if and only if every pair of vertices has at least ''k'' internally disjoint paths in between.

==Directed graphs==

All these statements in both edge and vertex versions remain true in directed graphs (when considering directed paths).

==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.

== 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>

==Infinite graphs==
Menger's theorem holds for infinite graphs, and in that context it applies to the minimum cut between any two elements that are either vertices or [[end (graph theory)|ends]] of the graph {{harv|Halin|1974}}. The following result of [[Ron Aharoni]] and [[Eli Berger]] was originally a conjecture proposed by [[Paul Erdős]], and before being proved was known as the '''Erdős–Menger conjecture'''.
It is equivalent to Menger's theorem when the graph is finite.

:Let ''A'' and ''B'' be sets of vertices in a (possibly infinite) [[directed graph|digraph]] ''G''. Then there exists a family ''P'' of disjoint ''A''-''B''-paths and a separating set which consists of exactly one vertex from each path in ''P''.

==See also==
* [[Gammoid]]
* [[k-vertex-connected graph]]
* [[k-edge-connected graph]]
* [[Vertex separator]]

==References==
{{Reflist}}

==Further reading==
* {{cite journal
  | author = Menger, Karl
  | title = Zur allgemeinen Kurventheorie
  | journal = Fund. Math.
  | volume = 10
  | pages = 96–115
  | year = 1927| doi = 10.4064/fm-10-1-96-115
 | doi-access = free
  }}
* {{cite journal |doi=10.1007/s00222-008-0157-3 |title=Menger's theorem for infinite graphs |journal=Inventiones Mathematicae |volume=176 |pages=1–62 |year=2008 |last1=Aharoni |first1=Ron |last2=Berger |first2=Eli |issue=1 |arxiv=math/0509397 |bibcode=2009InMat.176....1A |s2cid=15355399 }}
*{{cite journal |doi=10.1007/BF02993589 |title=A note on Menger's theorem for infinite locally finite graphs |journal=Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg |volume=40 |pages=111–114 |year=1974 |last1=Halin |first1=R. |s2cid=120915644 }}

== External links ==
*[http://www.math.unm.edu/~loring/links/graph_s05/Menger.pdf A Proof of Menger's Theorem]
*[http://brain.math.fau.edu/locke/Menger.htm Menger's Theorems and Max-Flow-Min-Cut]

[[Category:Graph connectivity]]
[[Category:Network theory]]
[[Category:Theorems in graph theory]]