Menger's theorem

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

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.

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.

It is also a special case of the still more general (strong) duality theorem for linear programs.

A formulation that for finite digraphs is equivalent to the above formulation is: In this version the theorem follows in fairly easily from Kőnig's theorem: in a bipartite graph, the minimal size of a cover is equal to the maximal size of a matching.

Let P be the set of all AB-paths composed of edges uv in D such that u'v'' belongs to M. Let Q in the original graph consist of all vertices v such that both v' and v'' 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.