ein zusammenhängender GraphG mit mindestens k + 1 Ecken, so daß G − E′ für alle E′ ⊆ E(G) mit |E′| ≤ k − 1 (k ∈ ℕ) zusammenhängend bleibt.

Ist G k-fach zusammenhängend, aber nicht (k + 1)-fach zusammenhängend, so nennt man k = κ(G) Zusammenhangszahl von G. Für einen zusammenhängenden Graphen G gilt genau dann κ(G) = k, wenn die kleinste trennende Eckemenge aus k Ecken besteht oder G der vollständige Graph K_k+1 ist.

Im Jahre 1927 hat K.Menger die folgende berühmte und wichtige notwendige und hinreichende Bedingung für den k-fachen Zusammenhang eines Graphen entdeckt.

Ein Graph ist genau dann k-fach-zusammenhängend, wenn zwischen je zwei Ecken k kreuzungsfreie Wege existieren.

Dabei heißen k Wege von einer Ecke x zu einer anderen Ecke y kreuzungsfrei, wenn diese Wege bis auf x und y paarweise eckendisjunkt sind.

Aus der Mengerschen Charakterisierung ergibt sich unmittelbar ein Resultat von H. Whitney (1932), daß in einem 2-fach zusammenhängenden Graphen je zwei Ecken auf einem gemeinsamen Kreis liegen. Der Mengersche Satz führt auch schnell zu der nächsten Aussage, die ebenfalls auf H.Whitney (1932) zurückgeht.

Es gilt κ(G) ≤ λ(G) ≤ δ(G), wobei λ(G) die Kantenzusammenhangszahl und δ(G) der Minimalgrad bedeuten.