Definice:
- hranový řez v grafu je je nesouvislý.
- vrcholový řez v grafu je je nesouvislý.
- hranová souvislost
- vrcholová souvislost
- Graf je hranově -souvislý platí-li .
- Graf je vrcholově -souvislý platí-li .
- Takovému maximálnímu říkáme pak kriticky souvislý.
Mengerovy věty
Věta: (hranová verze, Ford-Fulkerson) Pro graf , a platí existuje alespoň hranově disjunktních cest. Důkaz: () Nechť existuje pro spor hranový řez . Tedy je rozdělení na více komponent. Vezmu-li teď z jedné komponenty a z druhé, tak mají z předpokladu alespoň hranově disjunktních cest a tedy řez nemohl přerušit všechny a tudíž to není řez a máme spor.
() Mějme a pro hledejme disjunktní cesty. Sestrojíme si pomocnou jednotkovou síť, kde beru jako zdroj a jako stok a nalezneme tok. Pak vidíme, že máme tok velikosti alespoň (maximální tok je minimální řez) a z toku naleznu cesty.
Věta: (vrcholová verze, Menger) Pro graf , a platí existuje alespoň vrcholově disjunktních cest, až na vrcholy . Důkaz: () Nechť existuje pro spor vrcholový řez . Tedy je rozdělení na více komponent. Vezmu-li teď z jedné komponenty a z druhé, tak mají z předpokladu alespoň vrcholově disjunktních cest a tedy řez nemohl přerušit všechny a tudíž to není řez a máme spor.
() Předpokládejme, že každá množina vrcholů, která *odřízne od , má velikost alespoň .
- Každý vrchol rozdělíme na dva: a , a přidáme hranu .
- Každou původní hranu nahradíme hranou .
- Vznikne orientovaná síť s jednotkovými kapacitami (každá hrana má kapacitu 1).
- V této síti hledáme maximální tok z do (Ford–Fulkerson).
- Z faktu, že každý vrcholový řez má kapacitu alespoň , plyne, že maximální tok má hodnotu alespoň .
- Každá jednotková cesta v toku odpovídá jedné vrcholově disjunktní cestě v původním grafu. Existuje alespoň vrcholově disjunktních -cest.