September 2015
Intermediate to advanced
415 pages
12h 24m
German
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 ...