Menger tételei

Egy $G$ irányított gráfban az $u$-ból $v$-be vezető élidegen utak maximális száma megegyezik az $u$-ból $v$-be vezető utakat lefogó élek minimális számával.

Egy $G$ gráfban az $u$-ból $v$-be vezető élidegen utak maximális száma megegyezik az $u$-ból $v$-be vezető utakat lefogó élek minimális számával.

Egy $G$ irányított gráfban $u$ és $v$ legyen két különböző nem szomszédos csúcs. Ekkor az $u$-ból $v$-be vezető pontidegen utak maximális száma megegyezik az $u$-ból $v$-be vezető utakat lefogó ($u$-tól és $v$-től különböző) pontok minimális számával.

Egy $G$ gráfban $u$ és $v$ legyen két különböző nem szomszédos csúcs. Ekkor az $u$-ból $v$-be vezető pontidegen utak maximális száma megegyezik az $u$-ból $v$-be vezető utakat lefogó ($u$-tól és $v$-től különböző) pontok minimális számával.