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 Statements Referenced by

Observed surface forms (1)

Surface form	Occurrences
Menger's theorem (graph theory)	0

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 NERFINISHED ⓘ
publishedIn	Fundamenta Mathematicae NERFINISHED ⓘ
relatedTo	Whitney's theorem on 2-connectivity NERFINISHED ⓘ edge connectivity ⓘ max-flow min-cut theorem NERFINISHED ⓘ 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 ⓘ

Referenced by (1)

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

Menger → notableFor → Menger theorem in graph theory ⓘ

subject surface form: Karl Menger