Separationen und Trenner

Definition. Sei $G$ ein Graph und $A, B \subseteq V (G)$ . Sei $X \subseteq V (G)$ .

$X$ trennt $A$ und $B$ in $G$ , oder $X$ ist ein $A$ – $B$ -Trenner, wenn jeder $A$ – $B$ -Pfad in $G$ einen Knoten aus $X$ enthält.
$X$ ist ein Trenner in $G$ , wenn $X$ zwei Knoten $u, v \notin X$ derselben Komponente von $G$ trennt.
Ein $k$ -Trenner in $G$ ist ein Trenner $X$ in $G$ mit $| X | = k$ .

Bemerkung. Sei $G$ ein Graph und sei $X \subseteq V (G)$ . Ist $X = {v}$ ein Trenner in $G$ , dann ist $v$ ein Schnittknoten in $G$ .
Beobachtung. Ein Graph $G$ ist also genau dann $k$ -zusammenhängend, wenn $| G | > k$ und es keinen Trenner $X \subseteq V (G)$ der Größe $| X | < k$ gibt, der zwei Knoten $u, v \in V (G) ∖ X$ trennt.

Beispiel: !DS_vollständiger_foliensatz, p.179