Definíció: Egy G grág elvágópontja egy olyan v pont, hogy c(G-v)>c(G).
Megjegyzés: c(G-v) sokkal nagyobb is lehet, mint c(G). Korábban láttuk, hogy egy él esetén c(G-e)> c(G) esetén c(G-e)=c(G)+1.
Megjegyzés: G gráf akkor és csak akkor kétszeresen összefüggõ ha összefüggõ, nincs benne elvágópont és legalább három pontja van.
Definíció: Egy e és egy f él ^ relációban van, ha azonosak vagy egy körön vannak.
Lemma: Az ^ reláció ekvivalenciareláció.
Bizonyítás: Egyszerû, könnyen meggondolható, de nem végezzük el.
A továbbiakban minden gráf EGYSZERÛ GRÁF lesz.
Tétel: A következõk (egy G egyszerû gráf esetén) ekvivalensek: (i) G kétszeresen összefüggõ (ii) G bármely két éle egy körön van, összefüggõ (speciálisan nincs benne izolált csúcs) és legalább három pontja van. (iii) G bármely u és v pontja között van két pontfüggetlen (vagy pontidegen) út (azaz olyan két uv út, aleyeknek nincs közös belsõ pontjuk) és legalább három pontja van.
Bizonyítás: (ii)=>(iii)=>(i) Egyszerû.
(i)=>(ii) G kétszeresen összefüggõ így
összefüggõ és legalább hárompontja
van.
A kétszeres összefüggõségbõl következik, hogy bármely két közös végponttal rendelkezõ él ^ relációban áll. Az összefüggõség alapján adódik, hogy bármely két él ^ relációban áll egymással.
Tétel: Egy tetszõleges G egyszerû gráf
élhalmaza F(1), ..., F(k) osztályokba sorolható úgy,
hogy
(i) F(i)={e} akkor és csak akkor ha e elvágóél.
(ii) Ha F(i) nem egyelemû, akkor G|F(i) kétszeresen összefüggõ
(G kétszeresen összefüggõ komponense, blokkja)
(iii) V csúcs, akkor és csak akkor tartozik több
G|F(i)-hez, ha elvágó pont.
(iv) Definiálunk egy segédgráfot: csúcsai
G blokkjai és elvágó élei (G|F(i)-k), illetve
az elvágópontok, az élei pedig azon (G|F(i))-v párok
(v elvágópont), amelyekre v a G|F(i) részgráf
csúcsa. Ekkor a segédgráf nem tartalmaz kört.
Megjegyzés: A blokkok a gráf kétszeresen élösszefüggõ komponenseinek struktúráját finomítja.
Tétel: G akkor és csak akkor kétszeresen összefüggõ, ha felépíthetõ egy körbõl nyilt fülek ragasztásával.
Definíció: G k-szorosan élösszefüggõ, ha minden k-nál kisebb elemszámú F élhalmazra G-F összefüggõ.
Definíció: G k-szorosan összefüggõ, ha minden k-nál kisebb elemszámú U ponthalmazra G-U összefüggõ és pontjainak száma legalább k+1.
Tétel: A következõk ekvivalensek (i) G k-szorosan élösszefüggõ, (ii) G bármely két pontja között van k darab páronként éldiszjunkt út.
Tétel: A következõk ekvivalensek (i) G k-szorosan összefüggõ, (ii) G bármely két pontja között van k darab páronként pontfüggetlen út és legalább k+1 pontja van.
A fenti két tétel (ii) => (i) iránya egyszerû. A másik irány bizonyítását késõbbre halasztjuk.
Definíció: G irányított gráf egy (V,E,K,B) négyes, ahol V a pontok (csúcsok) halmaza, E az élek halmaza, K és B egy-egy reláció a pontok és élek között (ki és be reláció) úgy, hogy minden élhez pontosan egy pont tartozik, ami vele K, és egy ami vele B relációban áll.
Megjegyzés: A fenti definíció szemléletesen azt jelenti, hogy ,,egy gráf mindegyik élére egy nyilat teszünk''.
Definíció: Kifok, befok.
Definíció: Irányított séta, vonal, út, kör egy G irányított gráfban.
Tétel (Menger-tétel):
(i) Legyen G egy irányított gráf és s,t
két különbözõ pontja. Ekkor
min{|F|: F élhalmazra G-F-ben nincs st irányított
út}
=max{k: G-ben létezik k darab páronként éldiszjunkt
irányított st út}.
(ii) Legyen G egy (irányítatlan) gráf és
s,t két különbözõ pontja. Ekkor
min{|F|: F élhalmazra G-F-ben nincs st út}
=max{k: G-ben létezik k darab páronként éldiszjunkt
st út}.
(iii) Legyen G egy irányított gráf és s,t
két különbözõ pontja, amelyre st nem él.
Ekkor
min{|U|: U s-et és t-t nem tartalmazó ponthalmazra G-U-ben
nincs st irányított út}
= max{k: G-ben létezik k darab páronként pontfüggetlen
irányított st út}.
(iv) Legyen G egy (irányítatlan) gráf és
s,t két különbözõ pontja, amelyre st nem él.
Ekkor
min{|U|: U s-et és t-t nem tartalmazó ponthalmazra G-U-ben
nincs st út}
= max{k: G-ben létezik k darab páronként pontfüggetlen
st út}
Bizonyítás: (iii)=>(iv) Legyen G, s,t egy (iv)-ben szereplõ hármas. Legyen H a G-bõl minden él megduplázásával és oda-vissza irányításával nyert gráf. Ekkor H, s, t-ra vonatkozó, (iii)-ban szereplõ minimalizálási, illetve maximalizálási probléma optimuma ugyan az lesz mint a G, s, t-re vonatkozó minimalizálási, illetve maximalizálási probléma optimuma. Ebbõl adódik az állítás.
(i)=>(ii) Legyen G, s,t egy (iv)-ben szereplõ hármas. Legyen H a G-bõl minden él megduplázásával és oda-vissza irányításával nyert gráf. Ekkor H, s, t-ra vonatkozó, (iii)-ban szereplõ minimalizálási, illetve maximalizálási probléma optimuma ugyan az lesz mint a G, s, t-re vonatkozó minimalizálási, illetve maximalizálási probléma optimuma. Ez azonban nem nyilvánvaló.
A minimalizálási feladatot átalakíthatjuk: Egy F elvágó élhalmazhoz tartozik az s-bõl G-F-ben elérhetõ pontok A halmaza. Ekkor az A-ból kilépõ éleket tartalmazza F, és egy optimális elvágó halmaz nem is tartalmaz mást. Így minimalizálásunk ekvivalens az s-et és t-t elválasztó A halmazok közül azon meghatározásával, amelyikre a kilápõ élek száma minimális. Ebben a formában a G-re illetve H-ra vonatkozó minimlizálási probléma ekvivalenciája nyilvánvaló.
A maximalizálási probléma esetén G-ben lévõ k éldiszjunkt útból könnyen nyerhetõ H-beli k éldiszjunkt út. Megfordítva is megtehetõ ez, és ebbõl adódik a hiányzó bizonyítás rész. Az indoklás azonban nem olyan egyszerû.
Legyen P(1), ..., P(k) éldiszjukt utak H-ban. Vegyük ezek élhalmazát és G pontjait. Az így kapott irányított gráf legyen S.
Az S gráfban igaz lesz Tulajdonság(k), ahol Tulajdonság(k)= s kifoka k, befoka 0. t kifoka 0, befoka k. Minden más pontra a kifok azonos a befokkal. A Tulajdonság(k) is már garantálja, hogy S-ben legyen k darab éldiszjunkt st út. Növeljünk egy s-bõl induló irányított vonalat (kezdjünk el egy tetszõleges sétát s-bõl, vigyázzunk arra, hogy ne ismételjünk élt és folytassuk addig, amíg el nem akadunk). Könnyû belátni, hogy csak t-ben akadhatunk el. Ezzel S-ben találtunk egy st irányított vonalat és így egy irányított utat is. Hagyjuk el ennek éleit S-bõL és ezzel egy Tulajdonság(k-1)-gyel rendelkezõ gráfot kapunk, amivel tovább folytathatjuk eljárásunkat, amíg célhoz nem érünk.
Ezekután S-bõl hagyjuk el az oda-vissza irányított élpárokat. Ezzel Tulajdonság(k) megmarad. Így a kiritkított S-ben is lesz még k éldiszjunkt st út. Ezeknek az utaknak megfelelõ utak G-ben éldiszjunktak lesznek.
(i)=>(iii) és (i) bizonyítása legközelebb.