Menger's theorem

Menger's theorem equates the maximum number of pairwise vertex-disjoint paths between two vertices with the minimum number of other vertices whose removal separates them.

Vertex-disjoint paths: Paths are vertex-disjoint when no vertex belongs to more than one of them. These are the paths counted on one side of Menger's equality.
Graph theory: Graph theory studies structures made of vertices joined by edges. Menger's theorem is a statement about paths and separation in graphs.
Karl Menger: Karl Menger was an Austrian-American mathematician whose work included topology, geometry, and graph theory. He published the theorem that bears his name in 1927.
Network reliability: Network reliability studies the likelihood that a network remains connected when components can fail. Disjoint paths quantify how many vertex failures a connection can withstand.
Edge connectivity: Edge connectivity is the minimum number of edges whose removal disconnects a graph or separates specified vertices. Its separators remove edges, unlike the vertex separators in this theorem.
Vertex cut: A vertex cut is a set of vertices whose removal disconnects specified vertices or separates specified regions of a graph. Removing a smallest such set gives the bottleneck counted on the other side.
Path (graph theory): A path in a graph is a sequence of distinct vertices in which consecutive vertices are adjacent. The theorem counts paths joining its specified endpoints.
Hassler Whitney: Hassler Whitney was an American mathematician whose work helped establish modern graph theory. His work developed connections between graph connectivity and disjoint paths.
Menger's theorem algorithm: A Menger's theorem algorithm finds either many disjoint paths or a small separating vertex set. The theorem's two equal quantities provide matching optimization certificates.
Vertex-disjoint paths problem: The vertex-disjoint paths problem asks for disjoint routes among multiple prescribed terminal pairs. The general multiple-pair problem is not characterized by this single-pair equality.

Linked from 8 pages