Mehrfacher Zusammenhang

Def: ein Graph G heißt k-fach knoten-zusammenhängend, falls $\forall$M $\subseteq$ V(G) : | M| < k $\Rightarrow$ $G &setmn#setminus;M$ ist zusammenhängend.

Festlegung: K_{n + 1} ist n-fach knoten-zshgd (aber nicht (n + 1)-fach).

Def: ein Graph G heißt k-fach kanten-zusammenhängend, falls $\forall$M $\subseteq$ E(G) : | M| < k $\Rightarrow$ $G &setmn#setminus;M$ ist zusammenhängend.

Es gilt: G 1-fach knoten-zsgh $\iff$ G 1-fach kanten-zshg $\iff$ G zshg.

Bemerkung: für k$\ge$2 sind die Begriffe k-fach knoten-zshg und k-fach kanten-zshg nicht äquivalent.

Satz: Wenn G k-fach knoten-zshgd, dann ist G k-fach kanten-zshg.