Menger's theorem

Last updated October 18, 2024

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.

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 for x and y (the minimum number of edges whose removal disconnects x and y) is equal to the maximum number of pairwise edge-disjoint paths from x to y.

The implication for the graph G is the following version:

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.

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 internally disjoint paths from x to y.

A consequence for the entire graph G is this version:

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 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:^[1] 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.

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₁ be the earlier and v₂ be the later vertex of e on such a path. Then v₁ is reachable from A but not from B in G−S−e, while v₂ is reachable from B but not from A.

Now, let S₁ = S ∪ {v₁}, and consider a minimum AS₁-separator T in G−e. Since v₂ is not reachable from A in G−S₁, T is also an AS₁-separator in G. Then T is also an AB-separator in G (because every AB-path intersects S₁). Hence it has size at least k. By induction, G−e contains an AS₁-connector C₁ of size k. Because of its size, the endpoints of the paths in it must be exactly S₁.

Similarly, letting S₂ = S ∪ {v₂}, a minimum S₂B-separator has size k, and there is an S₂B-connector C₂ of size k, with paths whose starting points are exactly S₂.

Furthermore, since S₁ disconnects G, every path in C₁ is internally disjoint from every path in C₂, 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₁v₂). 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₁, v₂, with all ingoing edges going to v₁, all outgoing edges going from v₂, and an additional edge from v₁ to v₂. 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 proofs are often correctness proofs for max flow algorithms. 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:

Let A and B be sets of vertices in a finite 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: 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'', and every edge uv by the edge u'v''; additionally, include the edges v'v'' 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''.

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'', 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'' 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.^[2]

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 ends of the graph ( 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) 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.

Related Research Articles

In computer science and optimization theory, the max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the source to the sink is equal to the total weight of the edges in a minimum cut, i.e., the smallest total weight of the edges which if removed would disconnect the source from the sink.

In graph theory, a cycle in a graph is a non-empty trail in which only the first and last vertices are equal. A directed cycle in a directed graph is a non-empty directed trail in which only the first and last vertices are equal.

In mathematics, Hall's marriage theorem, proved by Philip Hall, is a theorem with two equivalent formulations. In each case, the theorem gives a necessary and sufficient condition for an object to exist:

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

<span class="mw-page-title-main">Graph (discrete mathematics)</span> Vertices connected in pairs by edges

In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called vertices and each of the related pairs of vertices is called an edge. Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges.

In graph theory, an Eulerian trail is a trail in a finite graph that visits every edge exactly once. Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. The problem can be stated mathematically like this:

In graph theory, the Robertson–Seymour theorem states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering. Equivalently, every family of graphs that is closed under minors can be defined by a finite set of forbidden minors, in the same way that Wagner's theorem characterizes the planar graphs as being the graphs that do not have the complete graph K₅ or the complete bipartite graph K_3,3 as minors.

In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices which, by most definitions, are all distinct. A directed path in a directed graph is a finite or infinite sequence of edges which joins a sequence of distinct vertices, but with the added restriction that the edges be all directed in the same direction.

In mathematics, in the areas of order theory and combinatorics, Dilworth's theorem states that, in any finite partially ordered set, the maximum size of an antichain of incomparable elements equals the minimum number of chains needed to cover all elements. This number is called the width of the partial order. The theorem is named for the mathematician Robert P. Dilworth, who published it in 1950.

In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements that need to be removed to separate the remaining nodes into two or more isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network.

In the mathematical discipline of graph theory the Tutte theorem, named after William Thomas Tutte, is a characterization of finite undirected graphs with perfect matchings. It is a special case of the Tutte–Berge formula.

In graph theory, a connected graph is $k$ -edge-connected if it remains connected whenever fewer than $k$ edges are removed.

In graph theory, a haven is a certain type of function on sets of vertices in an undirected graph. If a haven exists, it can be used by an evader to win a pursuit–evasion game on the graph, by consulting the function at each step of the game to determine a safe set of vertices to move into. Havens were first introduced by Seymour & Thomas (1993) as a tool for characterizing the treewidth of graphs. Their other applications include proving the existence of small separators on minor-closed families of graphs, and characterizing the ends and clique minors of infinite graphs.

In graph theory, a connected graph $G$ is said to be $k$ -vertex-connected if it has more than $k$ vertices and remains connected whenever fewer than $k$ vertices are removed.

<span class="mw-page-title-main">Pseudoforest</span> Graph with at most one cycle per component

In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be connected to each other by a path of consecutive edges. A pseudotree is a connected pseudoforest.

In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of ⁠ $⁠$ vertices from an $n$ -vertex graph can partition the graph into disjoint subgraphs each of which has at most ⁠ $⁠$ vertices.

In matroid theory, a field within mathematics, a gammoid is a certain kind of matroid, describing sets of vertices that can be reached by vertex-disjoint paths in a directed graph.

In the mathematical field of graph theory, Hall-type theorems for hypergraphs are several generalizations of Hall's marriage theorem from graphs to hypergraphs. Such theorems were proved by Ofra Kessler, Ron Aharoni, Penny Haxell, Roy Meshulam, and others.

In graph theory, a balanced hypergraph is a hypergraph that has several properties analogous to that of a bipartite graph.

In graph theory, a rainbow-independent set (ISR) is an independent set in a graph, in which each vertex has a different color.

References

↑ Göring, Frank (2000). "Short proof of Menger's theorem". Discrete Mathematics. 219 (1–3): 295–296. doi: 10.1016/S0012-365X(00)00088-1 .
↑ Aharoni, Ron (1983). "Menger's theorem for graphs containing no infinite paths". European Journal of Combinatorics. 4 (3): 201–4. doi: 10.1016/S0195-6698(83)80012-2 .

External links

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Göring, Frank (2000). "Short proof of Menger's theorem". Discrete Mathematics. 219 (1–3): 295–296. doi: 10.1016/S0012-365X(00)00088-1 .

[2] Aharoni, Ron (1983). "Menger's theorem for graphs containing no infinite paths". European Journal of Combinatorics. 4 (3): 201–4. doi: 10.1016/S0195-6698(83)80012-2 .

[1]

[2]