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

Ist G k-fach kantenzusammenhängend, aber nicht (k + 1)-fach kantenzusammenhängend, so nennt man k = λ(G) Kantenzusammenhangszahl von G. Für einen zusammenhängenden Graphen G gilt genau dann λ(G) = k, wenn die kleinste trennende Kantenmenge aus k Kanten besteht.

Die Idee der folgenden Aussage stammt von K.Menger (1927), aber explizit wurde sie erst 1956 durch L.R. Ford und D.R. Fulkerson sowie P. Elias, A. Feinstein und C.E. Shannon angegeben.

Ein Graph ist genau dann k-fach kantenzusammenhängend, wenn zwischen je zwei verschiedenen Ecken k kantendisjunkte Wege existieren.

Bei der Konstruktion von „guten Einbahnstraßennetzen“ ist das folgende tiefliegende Ergebnis von Nash-Williams (1960) sehr nützlich.

Jeder 2k-fach kantenzusammenhängende Graph besitzt eine k-fach bogenzusammenhängende Orientierung.

Der Spezialfall k = 1, der nicht so schwierig zu beweisen ist, geht auf H.E. Robbins (1939) zurück.