Sei \(G = (V, E)\) ein Graph. Dann gilt:
- \(G\) is \(k\)-knoten-zusammenhängend\(\iff\)\(\forall u, v \in V, u \neq v\) gibt mindestens \(k\) intern-knotendisjunkte \(u\)-\(v\)-Pfade.
- \(G\) ist \(k\)-kanten-zusammenhängend\(\iff\)\(\forall u, v \in V, u \neq v\) gibt mindestens \(k\) kantendisjunkte \(u\)-\(v\)-Pfade.
