Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Menger's theorem
Summary
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.
Proved by Karl Menger in 1927, it characterizes the 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 strong duality theorem for linear programs.
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 for x and y (the minimum number of edges whose removal disconnects x and y) is equal to the maximum number of pairwise edge-independent paths from x to y.
Extended to all pairs: a graph is 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.
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 internally vertex-disjoint paths from x to y.
Extended to all pairs: a graph is 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 vertex-disjoint paths in between.
All these statements (in both edge and vertex versions) remain true in directed graphs (when considering directed paths).
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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.