Menger's theorem

The set of Menger is one of the classical results of graph theory . It was proven by Karl Menger in 1927 and establishes a connection between the number of disjoint paths and the size of separators in a graph. In particular, the global variant of the sentence also makes statements about the K-connection and the edge connection of a graph. The theorem is a generalization of König's theorem (1916), according to which in bipartite graphs the pairing number corresponds to the vertex coverage number .

Local version

If an undirected graph and are and subsets of , then the smallest thickness of a set of vertices separating from is equal to the greatest thickness of a set of disjoint - -paths ${\displaystyle G=(V,E)}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle V}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$

Set of subjects

If the set is assumed to be one-element, the so-called fan rate immediately follows : If a subset of and an element of , then the smallest thickness of a subset separating from is equal to the largest thickness of a - - fan . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle V}$ ${\displaystyle a}$ ${\displaystyle V\setminus B}$ ${\displaystyle a}$ ${\displaystyle B}$ ${\displaystyle X\subset V\setminus \{a\}}$ ${\displaystyle a}$ ${\displaystyle B}$

Global version

With the definition of the edge connection and the k connection the global version follows:

1. ${\displaystyle G}$is -contiguous if and only if there are disjoint paths between two nodes . ${\displaystyle k}$ ${\displaystyle G}$ ${\displaystyle k}$
2. ${\displaystyle G}$is -fold edge-connected if and only if there are edge- disjoint paths between two nodes . ${\displaystyle k}$ ${\displaystyle G}$ ${\displaystyle k}$

Alternative formulation

Occasionally one finds the sentence in the literature in one of the following formulations: If and are two different nodes of , then the following applies: ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle G}$

1. Are and not adjacent, the least cardinality is one of separating subset of equal to the maximum cardinality of a set of disjoint - paths in . ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle V\setminus \{a,b\}}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle G}$
2. The smallest thickness of a set of edges separating from is equal to the largest thickness of a set of edge- disjoint - -paths in . ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle Y\subset E}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle G}$

use

Menger's theorem is often used as an alternative definition of the terms edge connection and k-connection. Furthermore, the Max-Flow-Min-Cut-Theorem is derived from the sentence, which plays a central role in the theory of flows and cuts in networks .

See also

• Disjoint paths and cuts

literature

• Reinhard Diestel: graph theory . Springer, Berlin 2010, ISBN 978-3-642-14911-5 (354 pages).

Individual evidence

1. ^ Karl Menger: On the general curve theory . In: Fund. Math. . 10, 1927, pp. 96-115.