Menger's theorem

Menger's theorem is one of the classical results of graph theory. It was proved in 1927 by Karl Menger and provides a link between the number of disjoint paths and the size of separators in a graph ago. In particular, the global version of the theorem is also true statements about the K- context and the edge-connectivity of a graph. The set is a generalization of the King (1916 ), which in bipartite graph corresponds to the number of pairing vertex cover number.

Local Version

If an undirected graph and are subsets of and, the least cardinality is one of separating vertex set equal to the maximum cardinality of a set of disjoint - paths

Set of pockets

If you take the amount as a singleton, so deduces immediately the so-called set of pockets: Is a subset of and an element of, then the minimum cardinality of a subset of separating equal to the maximum cardinality of a - fan.

Global version

With the definition of the edge-connectivity and k- context then infers the global version:

Alternative formulation

Occasionally one finds the sentence in the literature in one of the following formulations: Are and two different nodes of, then:

Use

Menger's theorem is often used as an alternative definition of edge-connectivity and k-connectedness. Furthermore, the max -flow min-cut theorem derives from the set, which plays a central role in the theory of flows and cuts in networks.