Mit Hilfe dieses Satzes können wir nun eine zum Satz von Menger analoge Aussage für Kanten beweisen.
Satz. Es seien a, b Ecken eines ungerichteten Graphen. Dann gilt
W k(a, b) = Zk(a, b).
Beweis. Liegen a und b in verschiedenen Zusammenhangskomponenten von G, so ist die Aussage trivialerweise erfüllt. Somit kann man annehmen, dass G zusammenhängend ist. Nach dem Satz von Ford-Fulkerson und dem obigen Lemma gibt es einen a-b-Schnitt 
. Da alle Kanten die Kapazität 1 haben, ist 
ist eine trennende Kantenmenge für a, b. Somit gilt . Es sei nun S eine ...
Get Algorithmische Graphentheorie, 4th Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
