Menger theorem in graph theory

E735111

result in combinatorics theorem in graph theory

Menger's theorem in graph theory is a fundamental result that characterizes the connectivity between two vertices in a graph by equating the maximum number of pairwise internally disjoint paths between them with the minimum size of a vertex cut separating them.

Try in SPARQL Jump to: Surface forms Disambiguation Statements Elicitation Referenced by

All labels observed (3)

Label	Occurrences
Menger theorem	1
Menger theorem in graph theory canonical	1
Whitney's theorem on 2-connectivity	1

How this entity was disambiguated

This entity first appeared as the object of triple T8454639 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.

NED1 Entity disambiguation (via context triple) gpt-5-mini-2025-08-07

Target entity: Menger theorem in graph theory
Context triple: [Karl Menger, notableFor, Menger theorem in graph theory]

A. Erdős–Gallai theorem
The Erdős–Gallai theorem is a fundamental result in graph theory that characterizes which sequences of nonnegative integers can occur as the degree sequences of simple graphs.
B. Lipton–Tarjan separator theorem
The Lipton–Tarjan separator theorem is a fundamental result in graph theory that shows any planar graph can be efficiently divided into roughly equal parts by removing only a relatively small set of vertices, enabling faster algorithms for many computational problems.
C. Erdős on Graphs: His Legacy
Erdős on Graphs: His Legacy is a mathematical monograph by Fan Chung and Ronald Graham that surveys and extends Paul Erdős’s influential work in graph theory and combinatorics.
D. Erdős–Ko–Rado theorem
The Erdős–Ko–Rado theorem is a fundamental result in extremal combinatorics that determines the maximum size of a family of subsets of a finite set in which every pair of subsets has a non-empty intersection.
E. Erdős–Stone theorem
The Erdős–Stone theorem is a fundamental result in extremal graph theory that asymptotically determines the maximum number of edges in an n-vertex graph that avoids containing a given subgraph.
F. None of above. chosen
G. Unsure - the case is ambiguous/there is not enough information to decide.

NED2 Entity disambiguation (via description) gpt-5-mini-2025-08-07

Target entity: Menger theorem in graph theory
Target entity description: Menger's theorem in graph theory is a fundamental result that characterizes the connectivity between two vertices in a graph by equating the maximum number of pairwise internally disjoint paths between them with the minimum size of a vertex cut separating them.

A. Erdős–Gallai theorem
The Erdős–Gallai theorem is a fundamental result in graph theory that characterizes which sequences of nonnegative integers can occur as the degree sequences of simple graphs.
B. Lipton–Tarjan separator theorem
The Lipton–Tarjan separator theorem is a fundamental result in graph theory that shows any planar graph can be efficiently divided into roughly equal parts by removing only a relatively small set of vertices, enabling faster algorithms for many computational problems.
C. Erdős on Graphs: His Legacy
Erdős on Graphs: His Legacy is a mathematical monograph by Fan Chung and Ronald Graham that surveys and extends Paul Erdős’s influential work in graph theory and combinatorics.
D. Erdős–Ko–Rado theorem
The Erdős–Ko–Rado theorem is a fundamental result in extremal combinatorics that determines the maximum size of a family of subsets of a finite set in which every pair of subsets has a non-empty intersection.
E. Erdős–Stone theorem
The Erdős–Stone theorem is a fundamental result in extremal graph theory that asymptotically determines the maximum number of edges in an n-vertex graph that avoids containing a given subgraph.
F. None of above. chosen

Statements (48)

Predicate	Object
instanceOf	result in combinatorics ⓘ theorem in graph theory ⓘ
appliesTo	finite graphs ⓘ undirected graphs ⓘ
assumes	simple undirected graph in standard formulations ⓘ
characterizes	connectivity between two vertices in a graph ⓘ
equates	maximum number of pairwise internally vertex-disjoint paths between two vertices ⓘ minimum size of a vertex separator between the two vertices ⓘ
field	combinatorics ⓘ graph theory ⓘ
hasEdgeVersionStatement	for any two distinct vertices s and t, the maximum number of pairwise edge-disjoint s–t paths equals the minimum size of an s–t edge cut ⓘ
hasFormulation	edge version ⓘ global vertex version ⓘ local vertex version ⓘ
hasGeneralization	infinite graphs (with additional conditions) ⓘ
hasGlobalVertexVersionStatement	the vertex connectivity of a finite graph equals the minimum, over all pairs of distinct vertices, of the size of a smallest vertex cut separating them ⓘ
hasLocalVertexVersionStatement	for any two nonadjacent vertices s and t, the maximum number of pairwise internally vertex-disjoint s–t paths equals the minimum size of an s–t vertex cut ⓘ
hasProofMethod	combinatorial arguments ⓘ reduction to max-flow min-cut (modern proofs) ⓘ
implies	a graph is k-vertex-connected if and only if every pair of vertices has at least k internally vertex-disjoint paths between them ⓘ edge connectivity equals minimum size of an edge cut separating some pair of vertices ⓘ vertex connectivity equals minimum size of a vertex cut separating some pair of vertices ⓘ
influenced	development of connectivity theory in graphs ⓘ network flow theory ⓘ
involvesConcept	internally disjoint paths ⓘ separating set of edges ⓘ separating set of vertices ⓘ
isTaughtIn	advanced undergraduate graph theory courses ⓘ graduate combinatorics courses ⓘ
namedAfter	Karl Menger ⓘ
publishedIn	Fundamenta Mathematicae ⓘ
relatedTo	Whitney's theorem on 2-connectivity ⓘ linked to: Menger theorem in graph theory edge connectivity ⓘ max-flow min-cut theorem ⓘ vertex connectivity ⓘ
relates	maximum number of pairwise internally vertex-disjoint paths ⓘ minimum size of a vertex cut separating two vertices ⓘ
topic	disjoint paths ⓘ edge connectivity ⓘ edge cuts ⓘ graph connectivity ⓘ vertex connectivity ⓘ vertex cuts ⓘ
usedIn	flow networks ⓘ graph algorithms ⓘ network reliability theory ⓘ routing and communication networks ⓘ
yearProved	1927 ⓘ

How these facts were elicited

Referenced by (3)

Full triples — surface form annotated when it differs from this entity's canonical label.

Karl Menger → notableFor → Menger theorem in graph theory ⓘ

subject linked to: Menger

Menger's theorem (graph theory) → relatedTo → Whitney's theorem on 2-connectivity ⓘ

subject linked to: Menger theorem in graph theory

linked to: Menger theorem in graph theory

Robbins theorem → relatedTo → Menger theorem ⓘ