Aufgabe:
Sei \( G=(V, E) \) ein einfacher ungerichteter Graph. Die Kantenzusammenhangszahl \( \lambda(G) \) ist definiert als die minimale Anzahl an Kanten, die aus \( E \) entfernt werden müssen, damit der resultierende Graph nicht mehr zusammenhängend ist.
Problem/Ansatz:
2.1 Zeigen Sie, dass für alle \( k \in \mathbb{N} \) ein einfacher ungerichteter Graph \( G_{k} \) mit Kantenzusammenhangszahl \( \lambda\left(G_{k}\right)=k \) existiert.
2.2 Geben Sie ein Verfahren an, um mit der Lösung von höchstens \( n=|V| \) Max-Flow-Problemen auf \( G \) (bzw. seiner Darstellung als Digraph) die Kantenzusammenhangszahl \( \lambda(G \) ) zu bestimmen.
