In the mathematical discipline of graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

 and related areas, Menger's theorem is a basic result about connectivity

Connectivity (graph theory)

In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements which need to be removed to disconnect the remaining nodes from each other. It is closely related to the theory of network flow problems...

 in finite undirected graphs. It was proved for edge-connectivity

K-edge-connected graph

In graph theory, a graph is k-edge-connected if it remains connected whenever fewer than k edges are removed.-Formal definition:Let G =  be an arbitrary graph....

 and vertex-connectivity

K-vertex-connected graph

In graph theory, a graph G with vertex set V is said to be k-vertex-connected if the graph remains connected when you delete fewer than k vertices from the graph...

 by Karl Menger

Karl Menger

Karl Menger was a mathematician. He was the son of the famous economist Carl Menger. He is credited with Menger's theorem. He worked on mathematics of algebras, algebra of geometries, curve and dimension theory, etc...

 in 1927. The edge-connectivity version of Menger's theorem was later generalized by the max-flow min-cut theorem

Max-flow min-cut theorem

In 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 minimum capacity which when removed in a specific way from the network causes the situation that no flow can pass from the source to the...

.

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 theorem states that 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 path

Path (graph theory)

In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them...

s from x to y.

Extended to subgraphs: a maximal subgraph disconnected by no less than a k-edge cut is identical to a maximal subgraph with a minimum number k of edge-independent paths between any x, y pairs of nodes in the subgraph.

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 theorem states that the size of the minimum vertex cut for x and y (the minimum number of vertices whose removal disconnects x and y) is equal to the maximum number of pairwise vertex-independent path

Path (graph theory)

In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them...

s from x to y.

Extended to subgraphs: a maximal subgraph disconnected by no less than a k-vertex cut is identical to a maximal subgraph with a minimum number k of vertex-independent paths between any x, y pairs of nodes in the subgraph.

It is not too hard to show that Menger's theorem holds for infinite graphs. The following statement is equivalent to Menger's theorem for finite graphs and is a deep recent result of Ron Aharoni

Ron Aharoni

Ron Aharoni is an Israeli mathematician, working in finite and infinite combinatorics. Aharoni is a professor at the Technion – Israel Institute of Technology, where he received his Ph.D. in mathematics in 1979. With Nash-Williams and Shelah he generalized the marriage theorem by obtaining the...

 and Eli Berger for infinite graphs (originally a conjecture proposed by Paul Erdős

Paul Erdos

Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...

):
Let A and B be sets of vertices in a (possibly infinite) digraph

Directed graph

A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...

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.