Teorie grafů

Zde jsou moje zápisky z předmětu Teorie grafů, který přednášel v zimním semestru 2024 Jan Volec na FJFI ČVUT. Organizační informace jsou k dispozici na stránce předmětu.

Grafy

Definice Graf je uspořádaná dvojice (V,E), kde V je konečná množina vrcholů a E⊂(V2) je množina hran. Značíme V=V(G),E=E(G).
Definice Nulový graf je graf (∅,∅).
Definice Doplněk grafu G=(V,E) je graf G¯≔(V,(V2)∖E).
Definice Vrchol u∈V je incidentní s hranou e∈E, pokud u∈e. Hrany e,f∈E jsou incidentní, pokud |e∩f|=1.
Konvence Většinou budeme pro graf s n vrcholy volit V=[n]=n^.
Věta Počet různých grafů s n vrcholy je 2(n2).
Důkaz Máme celkem (n2) možných hran a každá tam může a nemusí být.
Definice Sousedství vrcholu v∈V je NG(v)≔{w∈V|{v,w}∈E}. Prvky sousedství jsou sousedé a velikost sousedství je stupeň vrcholu: degG(v)≔|NG(v)|.
Definice Nechť d∈ℕ0. Graf G je d-regulární, pokud ∀v∈V:degG(v)=d.
Věta o potřesení rukou
∑v∈VdegG(v)=2|E|.
Důkaz Jsou to dva různé způsoby, jak spočítat počet konců hran.
Definice Skóre grafu s vrcholy [n] je (d1,…,dn), kde di≔degG(i).
Věta Má-li graf n vrcholů, potom ∀i∈[n]:di<n.
Důkaz Máme pro každý vrchol jen n−1 možných sousedů.
Věta Nechť 0≤d1≤⋯≤dn<n. Potom existuje graf velikosti n se skórem (d1,…,dn), právě když existuje graf velikosti n−1 se skórem
(d1,d2,…,dn−dn−2,dn−dn−1,dn−dn−1,dn−dn+1−1,…,dn−2−1,dn−1−1).
Důkaz
(⇐)
Vezmeme graf, přidáme nový vrchol a spojíme ho s posledními dn vrcholy původního grafu.
(⇒)
Pro daný graf G označme j(G) největší číslo takové, že (vj,vn)∉E. Ze všech grafů se skórem (d1,…,dn) zvolme ten, pro který je j(G) minimální. Zjevně j(G)≥n−dn−1. Předpokládejme pro spor, že nerovnost je ostrá. Potom existuje i<j takové, že (vi,vn)∈E. Jelikož di≤dj, musí existovat k takové, že (vi,vk)∉E∧(vj,vk)∈E. Odstraníme-li hrany (vi,vn),(vj,vk) a přidáme (vj,vn),(vi,vk), dosteneme graf se stejným skórem a menším j, což je spor. Platí tedy j(G)=n−dn−1. To ale znamená, že stačí odebrat poslední vrchol a dostaneme graf s požadovaným skórem.

Izomorfismus grafů

Definice Grafy G,H jsou izomorfní, pokud mezi nimi existuje izomorfismus: bijektivní funkce f:V(G)→V(H) taková, že {u,w}∈E(G)⟺{f(u),f(w)}∈E(H). Značíme G≅H. Je-li G=H, jde o automorfismus. Množinu všech automorfismů grafu značíme Aut(G). Je-li Aut(G)={I}, graf je strnulý.
Věta Pro každý graf G je Aut(G) grupa.
Důkaz Triviální.
Definice Množinu tříd ekvivalence grafů s n vrcholy až na izomorfismus označíme 𝒢︀n.
Věta
2(n2)n!≤|𝒢︀n|≤2(n2).
Důkaz Horní odhad plyne z toho, že je tolik grafů celkem. Dokážeme dolní odhad: Máme:
2(n2)=∑G∈𝒢︀nn!|Aut(G)|≤|𝒢︀n|⋅n!,
kde rovnost plyne z toho, že jsou to dva různé způsoby, jak spočítat všechny grafy, a druhá plyne z toho, že každý člen sumy je nanejvýš n!.
Poznámka Jak moc dobrý je to odhad? Máme:
2(n2)=2n22⋅(1−1n),
n!≤nn=2nlog2n,
2(n2)n!≥2n22⋅(1−1n−2log2nn).

Sledy a souvislost

Definice Sled z vrcholu u∈V do vrcholu w∈V je posloupnost u=v0,e1,v1,e2,v2,…,vk−1,ek,vk=w taková, že vi∈V a ei={vi−1,vi}∈E. Číslo k je jeho délka. Sled, kde se neopakují hrany, je tah. Sled, kde se neopakují vrcholy, je cesta.
Věta Nechť u,w∈V. Potom následující tvrzení jsou ekvivalentní:
  1. Existuje sled z u do w.
  2. Existuje tah z u do w.
  3. Existuje cesta z u do w.
Důkaz Máme-li cestu, je to samozřejmě i tah a sled. Naopak máme-li sled, můžeme z néj odstranit všechny úseky, kde se vracíme někam, kde už jsme byli, a dostaneme cestu. Formálněji: Mezi všemi sledy z u do w zvolme ten s nejmenší délkou a snadno dokážeme, že je to cesta.
Definice Pokud existuje sled/tah/cesta z u∈V do w∈V, značíme u⇝w.
Věta Relace ⇝ je ekvivalence.
Důkaz Za domácí úkol.
Definice Třídy ekvivalence relace ⇝ jsou komponenty souvislosti grafu. Počet komponent souvislosti značíme comp(G). Je-li comp(G)=1, graf je souvislý. Počet různých (ne nutně neizomorfních) souvislých grafů s n vrcholy značíme sn.
Věta sn můžeme spočítat ze znalosti předchozích hodnot podle následujícího vzorečku:
∑i=1n(n−1i−1)⋅si⋅2(n−i2)=2(n2).
Důkaz Spočteme si dvěma způsoby, kolik je dvojic (G,v), kde G je graf s n vrcholy a v∈V(G). Zjevně je to 2(n2)⋅n. Teď se u každé dvojice podívejme na souvislou komponentu, ve které je vrchol v. Velikost této komponenty označíme i. Vybereme si, které vrcholy v ní jsou, který z nich je v, jak komponenta vypadá a jak vypadá zbytek grafu. Tím dostáváme
∑i=1n(ni)⋅i⋅si⋅2(n−i2)=2(n2)⋅n.
Podělením n dostaneme kýženou rovnost.

Základní grafy

Definice Úplný graf na n vrcholech je Kn≔([n],([n]2)).
Poznámka Úplný graf má n! automorfismů.
Definice Prázdný graf na n vrcholech je En≔([n],∅).
Poznámka Prázdný graf má n! automorfismů.
Definice Cesta na n vrcholech (délky n−1) je Pn≔([n],{{i,i+1}|i∈[n−1]}).
Poznámka Cesta má 2−δn,1 automorfismů.
Definice Cyklus na n vrcholech (délky n) je Cn≔([n],E(Pn)∪{{n,1}}).
Poznámka Cyklus má 2n automorfismů (konkrétně je to dihedrální grupa).

Podgrafy

Definice Graf H je podgraf grafu G, pokud V(H)⊂V(G) a E(H)⊂E(G). Je-li E(H)=E(G)∩(V(H)2), jde o indukovaný podgraf. Je-li V(H)=V(G), jde o faktor.
Poznámka Každý graf je podgraf sám sebe a jde o jediný indukovaný faktor.
Definice Cyklus v grafu G je podgraf H takový, že H≅Ck pro nějaké k≥3.

Nějaké další pojmy

Definice Nechť G je graf. Potom jeho minimální stupeň je δ(G)≔minv∈VdegG(v), maximální stupeň je Δ(G)≔maxv∈VdegG(v) a průměrný stupeň je avgdeg(G)≔2|E||V|.
Nevěta Každý graf s δ(G)≥1 je souvislý.
Nedůkaz Dokážeme indukcí přes počet vrcholů. Předpokládejme, že tvrzení platí pro všechny grafy s n vrcholy. Vezměme graf s n+1 vrcholy. Zvolíme-li vrchol, jistě bude spojený s nějakým jiným vrcholem. Podle indukčního předpokladu zbylých n vrcholů tvoří souvislý graf, takže i náš graf je souvislý.
Definice Nechť G=(V,E) je graf a e∈E. Potom G−e≔(V,E∖{e}).
Věta Nechť G=(V,E) je graf a e∈E. Potom comp(G−e)∈{comp(G),comp(G)+1}.
Důkaz Nechť e={u,w}. Pokud jsou u,w ve stejné komponentě souvislosti G−e, potom se na souvislosti nic nemění. Pokud jsou v různých komponentách, počet komponent se odebráním zvýšil o 1.
Definice Hrana e grafu G je most, pokud comp(G−e)=comp(G)+1.
Věta Hrana e grafu G není most, právě když leží na nějakém cyklu.
Důkaz
(⇐)
Pokud e={u,w} leží na kružnici, potom zjevně existuje i jiná cesta mezi u a w, tedy e není most.
(⇒)
Pokud e={u,w} není most, potom existuje cesta z u do w, která nevede přes e. Pokud k této cestě přidáme e, máme cyklus.

Stromy

Definice Nenulový graf G=(V,E) je strom, pokud platí jedna z ekvivalentních definic:
  1. G je souvislý a neobsahuje cyklus.
  2. Mezi každými dvěma vrcholy existuje právě jedna cesta.
  3. G je souvislý a všechny tahy jsou cesty.
  4. G neobsahuje cyklus a přidáním libovolné hrany vznikne cyklus.
  5. G je souvislý a každá hrana je most.
  6. G je souvislý a |V|=|E|+1.
  7. G neobsahuje cyklus a |V|=|E|+1.
Důkaz ekvivalence definic (1)–(5)
(1) ⇒ (2)
Nechť pro spor existují dvě různé cesty mezi dvěma danými body. Tyto cesty se v nějakém bodě musí rozejít a potom zase sejít. Spojením těchto dvou úseků vznikne cyklus.
(2) ⇒ (3)
Zjevně G je souvislý. Kdyby nějaký tah nebyl cesta, potom by obsahoval cyklus, takže by mezi některými dvěma grafy existovala cesta.
(3) ⇒ (4)
Kdyby G obsahoval cyklus, potom by to byl tah, který není cesta. Zároveň přidáním libovolné hrany vznikne cyklus, protože G je souvislý.
(4) ⇒ (5)
Kdyby G nebyl souvislý, mohli bychom spojit dvě komponenty hranou a nevzniknul by cyklus. Kdyby nějaká hrana nebyla most, potom by už existoval cyklus.
(5) ⇒ (1)
Žádná hrana není most, takže žádná hrana není obsažena v cyklu.
Definice Vrchol v grafu G je list, pokud degG(v)=1.
Lemma Každý strom s alespoň dvěma vrcholy má alespoň dva listy.
Důkaz Vezměme nejdelší cestu v grafu. Její konce už nejsou spojené s ničím dalším, protože je nejdelší a graf je acyklický, takže ty konce jsou listy.
Definice Nechť G=(V,E) je graf a v∈V. Potom G−v≔(V∖{v},E∖{{u,v}|u∈V}).
Věta Nechť G je souvislý graf a v∈V je list. Potom G−v je souvislý.
Důkaz Jednoduchý.
Důkaz ekvivalence (1) ⇔ (6) u definice stromu
(⇒)
Indukcí. Pro |V|=1 triviální. Je-li |V|≥2, potom existuje list. Po utržení tohoto listu dostaneme souvislý acyklický graf, takže strom. Na ten můžeme aplikovat indukční předpoklad. Opětovným přidáním listu zvýšíme |V| i |E| o 1, takže rovnost pořád bude platit.
(⇐)
Indukcí. Pro |V|=1 triviální. Pro indukční krok stačí dokázat, že existuje list, potom můžeme postupovat podobně jako u předchozího bodu. Kdyby graf neobsahoval list, potom δ(G)≥2, takže |E|≥|V|, což je spor s předpokladem.
Důkaz ekvivalence (?) ⇔ (7) u definice stromu Za domácí úkol.
Definice Faktor (V,F) souvislého grafu (V,E) je kostra, pokud (V,F) je strom.
Definice Počet různých stromů na n vrcholech, neboli koster Kn, označíme τn.
Věta Cayleyova formule
τn=nn−2.
Důkaz Pitmanův Označme τn′ počet zakořeněných stromů – dvojic (strom,vrchol). Zjevně τn′=n⋅τn. U každého zakořeněného stromu můžeme u všech hran nakreslit šipky směřující od kořene, čímž se z něj stane orientovaný graf. Také označme τn″ počet označkovaných zakořeněných stromů – ke každé hraně zakořeněného stromu nakreslíme jedinečné číslo z [n−1]. Zjevně τn″=(n−1)!⋅τn′=n!⋅τn. Zbývá tedy dokázat, že τn″=n!⋅nn−2.

Začneme s prázdným grafem na [n]. Budeme postupně přidávat šipky označkované číslem aktuálního kroku, přičemž budeme dodržovat, že graf bude bez (neorientovaných) cyklů a do každého vrcholu povede nejvýše jedna šipka. Tímhle způsobem jednoznačně vytvoříme označkovaný zakořeněný strom.

Podívejme se, kolik máme v i-tém kroku způsobů, jak přidat šipku. Již existuje i−1 šipek. Zároveň se po přidání každé šipky sníží počet komponent souvislosti o 1, takže máme n−i+1 komponent souvislosti. Začít můžeme v libovolném z n vrcholů. Skončit musíme ve vrcholu, který leží v jiné komponentě a ještě do něj nevede šipka. Takový vrchol je v každé komponentě právě jeden, takže máme n−i možností. Tudíž počet možností, jak v i-tém kroku nakreslit šipku, je n⋅(n−i).

Celkový počet možností přes všechny kroky algoritmu je tedy ∏i=1n−1n⋅(n−i)=n!⋅nn−2, čímž je věta dokázána.

Důsledek Počet neizomorfních stromů na n vrcholech je alespoň
nn−2n!=(1−ℴ(1))⋅en2πnn+12⋅nn−2=(1−ℴ(1))⋅en2πn52.
Poznámka Ve skutečnosti je znám lepší odhad: C⋅αnn52, kde C≈0.535,α≈2.956.
Věta Počet neizomorfních stromů na n vrcholech je nejvýše 4nn.
Důkaz Dokážeme, že každý zakořeněný strom lze až na izomorfismus jednoznačně reprezentovat řetězcem vyvážených závorek (alias Dijckovým slovem). Strom zakódujeme jednoduše tak, že napíšeme postupně kódy všech podstromů a uzavřeme je do závorek. Možných řetězců závorek je 4n. Podělením n opět dostáváme odhad na počet nezakořeněných stromů (ale tentokrát už kvůli izomorfismu nemáme jednoznačný vztah mezi zakořeněnými stromy a dvojicemi (strom,vrchol)).
Poznámka Počet řetězců závorek můžeme spočíst přesně pomocí Catalanových čísel, viz moje poznámky z DIMA3. Z toho můžeme vymlátit o něco lepší odhad, který má shodou okolností ve jmenovateli také n52
Definice Nechť G=(V,E) je graf a e∈(V2). Potom značíme G+e≔(V,E∪{e}).
Věta Nechť T=(V,F) je kostra grafu G=(V,E) a e∈E∖F. Potom T+e obsahuje právě jeden cyklus CeT a pro všechny f∈E(CeT) je (T+e)−f kostra G.
Důkaz Triviální.
Definice CeT je fundamentální cyklus hrany e v grafu G vůči kostře T.
Definice Graf je sudý, pokud stupeň každého vrcholu je sudý.
Definice Nechť G=(V,E) je graf. Potom charakteristický vektor faktoru (V,F) je funkce v→F:E→ℤ2 definovaná jako v→F(e)≔[e∈F].
Poznámka Pokud si pevně očíslujeme hrany, můžeme identifikovat v→F∈ℤ2m, kde m je počet hran.
Definice Pro daný graf G definujme prostor cyklů
𝒞︀G≔{v→F|Fje sudý faktorG}.
Věta 𝒞︀G je vektorový podprostor ℤ2m.
Důkaz Jelikož máme těleso ℤ2, stačí ověřit uzavřenost na sčítání. Zjevně platí v→F1+v→F2=v→F1▵F2. Snadno ověříme, že jsou-li F1,F2 sudé faktory, potom F1▵F2 je také sudý faktor.
Věta Nechť T je kostra grafu G a C1,…,C|E|−|V|+1 jsou všechny fundamentální cykly v G vůči T. Potom (C1,…,C|E|−|V|+1) je báze 𝒞︀G.
Důkaz Uvažujme bez újmy na obecnosti, že E∖E(T)={e1,…,e|E|−|V|+1}. Pro každé Ci platí, že je to jediný fundamentální cyklus, který obsahuje hranu ei, takže jsou lineárně nezávislé. Stačí dokázat, že generují celý prostor. Pro daný sudý faktor F definujme w→≔∑ei∈F∖E(T)v→Ci. Spočtěme součet w→+v→F. Zjevně prvních |E|−|V|+1 složek je 0. To znamená, že w→+v→F je charakteristický vektor nějakého sudého faktoru, jehož hrany jsou podmnožina T. Ale jediný takový faktor je prázdný graf, takže w→+v→F=0 neboli v→F=w→∈[C1,…,C|E|−|V|+1]λ.

Hledání minimální kostry grafu

Definice Vážený graf je trojice Gw=(V,E,w), kde (V,E) je graf a w:E→ℝ.
Věta Nechť Gw je vážený graf, přičemž w je prostá funkce. Potom existuje právě jedna kostra T taková, že ∑e∈E(T)w(e) je minimální.
Definice Této kostře říkáme minimální kostra.
Důkaz Nechť pro spor T1,T2 jsou dvě minimální kostry. Vezměme hranu f∈E(T1)▵E(T2) takovou, že w(f) je minimální. Bez újmy na obecnosti f∈T1∖T2. Jistě existuje nějaká hrana f2∈E(CT2f)∖T1. Jelikož f2∈E(T1)▵E(T2), musí být w(f2)>w(f). Potom ale T2−f2+f je kostra s menší váhou, což je spor.
Algoritmus Kruskalův pro hledání minimální kostry Pro daný vážený graf Gw seřaďme hrany tak, že w(e1)<⋯<w(em). Začneme s prázdným grafem Pro i=1,…,m se postupně podíváme, jestli by přidáním hrany ei vznikl cyklus, a pokud ne, tak ji přidáme.
Důkaz správnosti Zřejmě na konci vznikne kostra G. Nechť pro spor není minimální. Označme i index první hrany, kde se liší od minimální kostry. TBD
Definice Nechť Gw je vážený graf. Pro cestu P=(v0,e1,…,el,vl) definujeme váhu w(P)≔∑i=1lw(ei).
Definice Nechť Gw je vážený graf. Vzdálenost vrcholů u,v∈V je minimální váha cesty z u do v. Značíme distGw(u,v).
Věta distGw je metrika.
Důkaz Snadný.
Věta Nechť Gw je vážený graf a s∈V. Potom existuje acyklický faktor Ts takový, že pro všechny v∈V je distGw(s,v)=distTs(s,v).
Důkaz Dijkstrův algoritmus Začnéme s grafem Ts=({s},∅). Podíváme se na všechny hrany mezi V(Ts),V∖V(Ts) a vybereme z nich tu, která by po přidání minimalizovala vzdálenost mezi s a nově přidaným vrcholem. Tuto hranu přidáme to Ts a opakujeme, až bude Ts obsahovat všechny vrcholy. Indukcí dokážeme, že v každém kroku bude Ts mít požadovanou vlastnost. TBD

Multigrafy

Definice Multigraf je něco jako graf, ale mezi danou dvojicí vrcholů může vést víc hran, tedy E je multimnožina. Také ho můžeme chápat jako vážený graf, kde w:E→ℕ+ udává násobnost hrany.
Konvence Multimnožinu budu pro odlišení od množiny značit dvojitými složenými závorkami, např. ⦃2,3,3,4⦄.
Definice Multigraf (V,E,w) je souvislý, pokud graf (V,E) je souvislý.
Definice Cyklus délky 2 je multigraf ({1,2},⦃{1,2},{1,2}⦄).
Definice Počet koster grafu G je překvapivě počet jeho koster. Značíme T(G).
Definice Úplný graf bez jedné hrany je Kn−≔Kn−{1,2}.
Příklad
Definice Nechť G=(V,EM) je multigraf a e={x,y}∈E. Potom multigrafová kontrakce hrany e bez smyček je G/E≔(V∖{x,y}∪{z},EM′), kde
EM′=EM−⦃f∈EM|x∈f∨y∈f⦄+⦃{u,z}|u∉{x,y},({u,x}∈EM∨{u,y}∈EM)⦄.
Lidsky řečeno, konce hrany e „spojíme“ do jednoho vrcholu.
Věta Nechť G=(V,EM) je multigraf a e∈EM. Potom T(G)=T(G−e)+T(G/e).
Důkaz Zjevně stačí dokázat, že T(G/e) je rovno počtu koster G, které obsahují e. Z každé kostry G obsahující e můžeme e odstranit a tím dostat kostru G/e. Naopak ke každé kostře G/e můžeme e přidat.

Bipartitní grafy

Definice Graf G=(V,E) je bipartitní, pokud existuje rozklad V=L⊎R takový, že ∀e∈E:e={l,r},l∈L,r∈R.
Lemma Každý strom je bipartitní.
Důkaz Zvolíme nějaký kořen a seskupíme vrcholy podle parity jejich vzdálenosti od kořene.
Lemma Podgraf bipartitního grafu je bipartitní.
Důkaz Triviální.
Definice Nechť G=(V,E) je graf. Množina W⊂V je nezávislá v G, pokud podgraf indukovaný W je prázdný, tedy neexistuje hrana spojující dva vrcholy z W.
Definice Tah v0,e1,…,vl je uzavřený, pokud v0=vl
Věta Následující tvrzení o grafu G jsou ekvivalentní:
  1. G je bipartitní.
  2. G neobsahuje uzavřený tah liché délky.
  3. G neobsahuje indukovaný lichý cyklus.
  4. G neobsahuje lichý cyklus.
Důkaz
(1) ⇒ (2)
Jdeme-li v bipartitním grafu podél tahu, musí se vrcholy střídat mezi L a R. Takže aby to vyšlo, uzavřený tah musí mít sudou délku.
(2) ⇒ (3)
Triviální.
(3) ⇒ (4)
Předpokládejme pro spor, že existuje lichý cyklus, ale neexistuje indukovaný lichý cyklus. Vezměme nejkratší cyklus. Jelikož není indukovaný, exisuje mezi nějakými dvěma jeho vrcholy hrana „napříč“. Z této hrany a části původního cyklu můžeme vytvořit dva nové cykly, které jsou kratší a jeden z nich má lichou délku. To je spor.
(4) ⇒ (1)
Bez újmy na obecnosti můžeme předpokládat, že G je souvislý. Vezměme jeho kostru T. Tato kostra je bipartitní, tedy můžeme podle ní rozdělit vrcholy na L a R. Stačí zkontrolovat, že hrany, které nejsou v T, respektují toto rozdělení. Každá taková hrana má fundamentální cyklus, který podle předpokladu má sudou délku, takže to vyjde správně.
Věta Každý graf (V,E) obsahuje bipartitní faktor (V,F) takový, že |F|≥⌈|E|2⌉.
Důkaz Mezi všemi bipartitními faktory zvolíme ten s nejvíce hranami. Dokážeme, že pro každý vrchol v∈V je degF(v)≥degE(v)2, z toho už tvrzení triviálně plyne. Předpokládejme pro spor, že pro nějaké v∈V je degF(v)<degE(v)2. Potom ale přesunutím v do druhé komponenty můžeme počet hran zvýšit, což je spor.

And now for something completely different

Věta Každý graf G=(V,E) obsahuje indukovaný podgraf H s δ(H)>|E||V|.
Důkaz Budeme postupně odebírat vrcholy, které mají zrovna nejmenší stupeň. Nechť di je počet hran, které zmizí v i-tém kroku. TBD

Rozklad grafu

Definice Nechť G je graf. Množina podgrafů {H1,…,Hm} rozkládá G, pokud ∀e∈E,∃1i∈[m]:e∈E(Hi).
Věta Je-li {H1,…,Hm} rozklad Kn, přičemž každé Hi je úplný podgraf s nejvýše n−1 vrcholy, potom m≥n.
Důkaz Vytvoříme si matici M∈{0,1}n×m, kde Mi,j≔[i∈V(Hj)]. Potom (MM𝖳)i,j=1 pro i≠j a (MM𝖳)i,i je počet Hj takových, že i∈Hj. To musí být aspoň 2, jinak je porušena podmínka, že Hj nemá n vrcholů. Tudíž můžeme psát MM𝖳 jako součet jedničkové matice a kladné diagonální matice. Z toho plyne, že MM𝖳 je pozitivně definitní a tedy regulární. Celkově máme n=h(MM𝖳)≤h(M)≤m.
Poznámka Snadno se přesvědčíme, že v nerovnosti pro každé n může nastat rovnost.
Definice Bipartitní graf G=(V,E),V=L∪R je úplný bipartitní, pokud E={{l,r}|l∈L,r∈R}. Značíme G=K|L|,|R|.
Věta Graham-Pollak Je-li {H1,…,Hm} rozklad Kn, přičemž každé Hi je úplný bipartitní podgraf, potom m≥n−1.
Důkaz Nechť to pro spor jde pro m≤n−2. Sestavíme m+1 rovnic o n neznámých:
∑j=1nxj=0,
∀i∈[m]:∑j∈L(Hi)xj=0.
To je homogenní soustava lineárních rovnic, která má více neznámých než rovnic, takže má nenulové řešení xj=cj. Potom
0=(∑j=1ncj)2=∑j=1ncj2+2∑1≤j<k≤ncjck.
Stačí dokázat, že ∑1≤j<k≤ncjck=0, čímž dostaneme spor. Využijeme toho, že Hi tvoří rozklad:
∑1≤j<k≤ncjck=∑i=1m(∑j∈L(Hi)cj)(∑k∈R(Hi)ck)=0.
Poznámka Snadno se přesvědčíme, že v nerovnosti pro každé n může nastat rovnost.

Matice grafu

Definice Matice sousednosti multigrafu G=([n],E,w) je matice AG∈ℕ0n×n definovaná jako (AG)i,j≔w({i,j}), kde jako váhu neexistující hrany bereme 0.
Věta Nechť G je multigraf a k∈ℕ0. Potom (AGk)i,j je počet sledů délky k z vrcholu i do vrcholu j.
Důkaz Snadno dokážeme indukcí z definice součinu matic.
Definice Matice incidence multigrafu G=([n],E,w) je matice BG∈{0,1}n×m, kde m≔∑e∈Ew(e) (počet hran včetně násobnosti) a e1,…,em jsou hrany, definovaná jako Bi,j≔[i∈ej].
Věta Nechť G je multigraf. Potom BG⋅BG𝖳=diag(degG(1),…,degG(n))+AG.
Důkaz Triviální.
Definice Spektrum grafu G je množina vlastních čísel AG.
Věta Courant-Weyl-Fisher Nechť A je symetrická reálná matice n×n a λ1 je její nejvyšší vlastní číslo. Potom
λ1=maxx∈ℝnx𝖳Ax‖x‖22.
Poznámka Jde o speciální případ věty o lokalizaci spektra z funkcionální analýzy, kde jako Hilbertův prostor volíme ℝn se standardním skalárním součinem.
Věta Nechť G je graf a λ1 je jeho největší vlastní číslo. Potom Δ(G)≥λ1≥avgdeg(G)≥δ(G).
Důkaz TBD
Důsledek Pro d-regulární graf je λ1=d.
Věta Nechť G=([n],E) je souvislý graf s alespoň dvěma vrcholy, λ1 je největší vlastní číslo AG a v je příslušný vlastní vektor. Potom buď v>0, nebo v<0.
Důkaz Nechť bez újmy na obecnosti ‖v‖2=1. Potom
λ1=‖v‖22λ1=λ1v𝖳v=v𝖳AGv.
Zvolme x≔(|v1|,…,|vn|). Podle Courant-Weyl-Fisherovy věty platí x𝖳AGx≤λ1. Navíc
x𝖳AGx=2∑{i,j}∈Exixj=2∑{i,j}∈E|vi||vj|≥|∑{i,j}∈Evivj|=λ1.
Z toho plyne, že všude nastává rovnost, takže buď v≥0, nebo v≤0. Stačí dokázat, že v neobsahuje nuly. Uvažujme bez újmy na obecnosti, že v≥0. Označme V+≔{i|vi>0} a V⊘≔{i|vi=0}. Nechť pro spor V⊘≠∅. Jelikož G je souvislý, jistě existuje z∈V⊘, které je spojené hranou s nějakým i∈V+, bez újmy na obecnosti z=1. Pro ε>0 zvolme y≔(ε,|x2|,…,|xn|). Potom
λ1≥y𝖳AGy‖y‖22≥x𝖳AGx+εvi‖y‖22=λ1+εvi1+ε2.
To pro ε<viλ1 bude ostře větší než λ1, čímž dostáváme spor.
Důsledek Nechť G je souvislý graf. Potom geometrická násobnost nejvyššího vlastního čísla AG je 1.
Důkaz Předpokládejme pro spor, že existují dva kolmé vlastní vektory v,w. Potom
0=v𝖳w=∑i=1nviwi.
To je součet nenulových čísel se stejným znaménkem, takže to nemůže být nula.
Věta Nechť G=([n],E) je souvislý graf se spektrem (λ1,…,λn). Potom λn=−λ1, právě když G je bipartitní.
Důkaz
(⇐)
Za domácí úkol.
(⇒)
Nechť w je vlastní vektor k λn. Bez újmy na obecnosti ‖w‖2=1. Dokážeme, že v≔(|w1|,…,|wn|) je vlastní vektor k λ1. Máme
−λ1=λn=w𝖳AGw=2∑{i,j}∈Ewiwj,
λ1=2|∑{i,j}∈Ewiwj|≤2∑{i,j}∈E|wi||wj|≤w1.
Aby nastala všude rovnost, musí všechny sčítance mít stejné znaménko. TBD
Věta Nechť G=([n],E) je souvislý d-regulární graf se spektrem d,λ2,…,λn a v1,…,vn jsou příslušné vlastní vektory. Potom pro všechna i≠1 je ∑j=1n(vi)j=0.
Důkaz TBD
Důsledek Spektrum je zároveň n−d−1,−λn−1,…,−λ2−1.
Důkaz Nechť I značí jednotkovou matici a J značí jedničkovou matici. Máme J=AG+AG¯+I. Předpokládejme, že G je souvi
Definice Laplaceova matice multigrafu G=([n],E,w) je matice LG∈ℕ0n×n definovaná jako (LG)i,j≔−w({i,j}), kde jako váhu neexistující hrany bereme 0 a za (LG)i,i volíme degG(i).
Věta Pro Laplaceovu matici multigrafu platí LG=BG⋅BG𝖳−2AG.
Důkaz Triviální.
Věta Laplaceova matice multigrafu je singulární.
Důkaz Sečteme všechny řádky.
Věta Laplaceova matice multigrafu je pozitivně semidefinitní.
Důkaz
x𝖳LGx=−2∑{i,j}∈Exixj+∑i=1ndegG(i)xi2=∑{i,j}∈E(xi−xj)2≥0.
Věta Pro multigraf G=([n],E) platí h(LG)=n−1, právě když je souvislý.
Důkaz
(⇒)
Je-li G nesouvislý, můžeme po permutaci vrcholů psát blokově
LG=(LG100LG2).
Potom h(LG)=h(LG1)+h(LG2)≤n−2.
(⇐)
TBD
Definice Nechť M je n×n matice. Potom M(i) značí matici M s odstraněným i-tým řádkem a sloupcem.
Poznámka Všimněme si, že pro matici sousednosti je AG(i)=AG−i, ale pro Laplaceovu matici to neplatí!
Věta Kirchoffova Počet koster grafu G=([n],E,w) můžeme pro libovolné i∈[n] spočítat jako T(G)=detLG(i).
Důkaz Je-li G nesouvislý, potom T(G)=0. Zároveň jeho Laplaceova matice sestává ze dvou menších Laplaceových matic, z nichž jedna zůstane netknutá, takže determinant bude 0. Předpokládejme tedy, že G je souvislý. Použijeme indukci podle počtu hran. Pro |E|=0 triviální. Jinak bez újmy na obecnosti uvažujme i=1 (jinak si můžeme přepermutovat vrcholy). Zvojme nějakou hranu vycházející z vrcholu 1, bez újmy na obecnosti e≔{1,2}. Její násobnost označme w. Pro nějaká v1,v2,τ máme
LG=(degG(1)−wv1𝖳−wdegG(2)v2𝖳v1v2τ).
Označme F≔G−e,H≔G/e. Pro ně máme
LF=(degG(1)−11−wv1𝖳1−wdegG(2)−1v2𝖳v1v2τ),
LH=(degG(1)+degG(2)−2wv1𝖳+v2𝖳v1+v2τ).
Podle indukčního předpokladu je T(F)=detLF(1)=det(degG(2)−1v2𝖳v2τ) a T(H)=detLH(1)=detτ=det(1v2𝖳0τ). Podle dříve dokázaného rekurzivního vzorce pro T máme
T(G)=T(F)+T(H)=det(degG(2)−1v2𝖳v2τ)+det(1v2𝖳0τ)=det(degG(2)v2𝖳v2τ)=detLG(1).

Eulerovské tahy

Definice Eulerovský tah v multigrafu je uzavřený tah, který obsahuje všechny hrany.
Věta Eulerova V multigrafu bez izolovaných vrcholů existuje eulerovský tah, právě když je souvislý a sudý.
Důkaz
(⇒)
Triviální.
(⇐)
Nechť T=v0e1v1⋯vl je nejdelší možný tah. Kdyby T nebyl uzavřený, potom by obsahoval lichý počet hran vycházejících z v0, což podle předpokladu nejsou všechny, takže by bylo možné ho prodloužit. Tedy T je uzavřený. Zbývá dokázat, že obsahuje všechny hrany. Předpokládejme, že neobsahuje. Vezměme libovolnou hranu e={u,v}, která není obsažena v T, ale T prochází vrcholem u (taková musí existovat, protože graf je souvislý). Pokud si tah přecyklíme tak, že u bude poslední vrchol, potom tah můžeme prodloužit o e, což je spor.
Důsledek V grafu bez izolovaných vrcholů existuje tah procházející všechny hrany, právě když je souvislý a má nejvýše dva vrcholy lichého stupně.
Důkaz Neobsahuje-li žádné vrcholy lichého stupně, stačí vzít eulerovský tah. Jeden vrchol lichého stupně obsahovat nemůže podle věty o potřesení rukou. Obsahuje-li dva vrcholy lichého stupně, propojíme je hranou, najdeme eulerovský tah a hranu znovu odstraníme.

Hamiltonovské kružnice

Definice Graf je hamiltonovský, pokud obsahuje cyklus procházející všechny vrcholy (hamiltonovskou kružnici).
Příklad Příklady hamiltonovských grafů: Cn pro n≥3, Kn pro n≥3, Kn,n pro n≥2.
Poznámka Na rozdíl od eulerovského tahu nelze efektivně určit, jestli je graf hamiltonovský. Konkrétně je to NP-úplná úloha.
Věta Ore Nechť graf G=(V,E),|V|≥3 splňuje podmínku
∀u,v∈V:{u,v}∉E⟹degG(u)+degG(v)≥|V|,
potom je hamiltonovský.
Důkaz Indukcí přes počet hran doplňku cˇ. Pro nulu to zjevně platí (úplný graf je hamiltonovský). Nechť cˇ≥1. Uvažujme graf G s (|V|2)−cˇ hranami splňující podmínku. Pro libovolnou e={u,w}∈E(G¯) označme G+≔G+e. Ten podle indukčního předpokladu obsahuje hamiltonovskou kružnici C. Pokud tato kružnice nepoužívá hranu e, jsme hotovi. Předpokládejme tedy, že C postupně prochází vrcholy w=v0,v1,…,vn−2,vn−1=u. Zkusíme najít i takové, že {vi−1,u},{vi,w}∈E(G). Tím budeme mít hamiltonovskou kružnici procházející postupně u=vn−1,vn−2,vn−3,…,vi,w=v0,v1,v2,…,vi−1. Definujme
A≔{vi|{vi−1,u}∈E(G)}⊂{v2,…,vn},
B≔NG(w)⊂{v1,…,vn−2}.
Tedy |A∪B|≤|{v1,…,vn−1}|=n−1. Zároveň podle předpokladu je |A|,|B|≥n2. Podle 🐦holubníkového principu🐦 existuje i takové, že vi∈A∩B, což je přesně to i, které jsme hledali.
Důsledek Dirac Má-li graf G=(V,E),|V|≥3 minimální stupeň alespoň |V|2, potom je hamiltonovský.
Věta Nechť v grafu G=(V,E) existují vrcholy X⊂V takové, že V∖X indukuje podgraf s více než |X| komponentami souvislosti. Potom G není hamiltonovský.
Důkaz Dokážeme obměnénou implikaci. Nechť G je hamiltonovský, ∅≠X⊂V a H≔G−X. Dokážeme, že H má nanejvýš |X| komponent. TBD

Robustní souvislost

Definice Artikulace v grafu G je vrchol v∈V(G) takový, že G−v má více komponent souvislosti než G.
Definice Graf s alespoň třemi vrcholy je neseparovatelný, pokud je souvislý a neobsahuje artikulaci.
Příklad Příklady neseparovatelných grafů: Kn pro n≥3, Cn pro n≥3, Ka,b pro a,b≥2, Petersenův graf
Lemma Obsahuje-li souvislý graf s alespoň třemi vrcholy most, potom obsahuje artikulaci.
Důkaz Na alespoň jedné straně mostu jsou alespoň dva vrcholy. Odebereme-li vrchol na konci mostu, přetrhne se nám to.
Věta Graf G je neseparovatelný, právě když každé dva vrcholy jsou spojit dvěma různými cestami, které až na konce nemají společný vrchol. Neboli každé dva vrcholy leží na nějaké kružnici.
(⇐)
Zjevně G je souvislý a obsahuje alespoň tři vrcholy. Stačí tedy dokázat, že neobsahuje artikulaci. To plyne z toho, že pokud odstraníme nějaký vrchol, tak mezi každými dvěma ostatními pořád existuje alespoň jedna cesta.
(⇒)
Indukcí podle d≔distG(u,v) dokážeme, že mezi každými dvěma vrcholy u,w existují dvě cesty. Je-li d=1, potom {u,w}∈E. Podle předpokladu {u,w} není most, takže existuje ještě nějaká jiná cesta. Nechť d≥2, P je nějaká cesta mezi u,w délky d a v je její předposlední vrchol. Podle indukčního předpokladu existují dvě vnitřně vrcholově disjunktní cesty P1,P2 mezi u,v. Jelikož v není artikulace, existuje také cesta Q z u do w neobsahující v. Označme x poslední vrchol Q ležící na P1 nebo P2. Je-li x=u, potom Q a u→P1v→w jsou hledanými cestami. Jinak bez újmy na obecnosti x∈V(P1)∖V(P2). Potom hledanými cestami jsou u→P2v→w a u→P1x→Qw.
Definice Nechť G=(V,E) je graf a e={u,w}∈E. Potom podrozdělení hrany e je graf G:e získaný tím, že doprostřed e nakreslíme nový vrchol ve, tedy G:e≔G−e+{u,ve}+{ve,w}.
Lemma Graf G=(V,E) je neseparovatelný, právě když G:e je neseparovatelný pro všechny e∈E.
Důkaz
(⇐)
Nechť u,w∈V. Podle předpokladu existují dvě vnitřně vrcholově disjunktní cesty mezi u,w v G:e. Pokud ani jedna z nich neobsahuje e, můžeme je použít i v G. Pokud jedna z nich obsahuje e, nahradíme ji dvěma nově vzniklými hranami.
(⇒)
Dokážeme, že libovolný vrchol x∈V(G:e) není artikulace. Je-li x=ve, potom (G:e)−x=G−e. Jelikož e podle předpokladu není most, vzniklý graf je souvislý. Je-li x∈e, potom (G:e)−x=G−x+list. Je-li x∈V∖e, potom (G:e)−x≃(G−x):e.
Definice Hrany e,f grafu jsou v relaci ∼B, pokud e=f nebo existuje cyklus obsahující e,f.
Věta Relace ∼B je ekvivalence.
Důkaz Reflexivita a symetrie plynou přímo z definice. Stačí dokázat tranzitivitu. Nechť {a,b}=e∼Bf∼Bg={α,β}. Označme Ce,f,Cf,g společné kružnice, x první společný vrchol Ce,f a „dlouhého oblouku“ Cf,g na cestě mezi α,β a y to samé z β do α. TBD
Definice Ucho ke grafu G ve vrcholech u,w∈V délky k∈ℕ je cesta P=(u=v0),e1,…,ek,(vk=w), kde vi∉V pro i=1,…,k−1.
Věta ušaté lemma Graf G je neseparovatelný, právě když existuje posloupnost grafů G0,…,Gt taková, že G0≃Ck,Gt≃G a každé Gi+1 vznikne z Gi přidáním ucha.
Důkaz Implikace (⇐) je triviální. Dokážeme (⇒) indukcí přes počet hran. Pro ‖E‖=3 triviální. Nechť G0 je libovolný cyklus v G. Začneme s i=0. Nechť F je množina, které neleží v Gi. Pokud existuje nějaká e∈F,e⊂Vi, potom zvolíme Gi+1≔Gi+e. Jinak jistě existuje nějaká e1∈F taková, že |e1∩Vi|=1. Označme v0 konec e1 ležící ve Vi a v1 konec e1 neležící v ei. Jelikož G je neseparovatelný, jistě v G−v0 existuje cesta z v1 do nějakého w∈Vi. Vezmeme nejkratší takovou cestu, přidáme k ní v0 a tím máme ucho. Opakujeme, až vytvoříme celé G.
Definice Nechť G=(V,E) a u,w∈V. Potom pG(u,w) je maximální počet vnitřně vrcholově disjunktních cest z u do w.
Definice Graf G=(V,E) je (vrcholově) k-souvislý, jestliže pro všechny vrcholy u,w∈V je pG(u,w)≥k.
Poznámka Graf je 1-souvislý, právě když je souvislý. Graf je 2-souvislý, právě když je neseparovatelný.
Definice Nechť G=(V,E) je graf. Potom κ(G) je největší k takové, že G je k-souvislý.
Poznámka Zjevně platí |V|≥κ(G)+1. Pro úplný graf se nabývá rovnosti.
Definice Nechť G=(V,E) a u,w∈V,{u,w}∉E. Potom cG(u,w) je minimální velikost množiny W takové, že v G−W neexistuje cesta z u do w.
Definice Separátor v souvislém grafu G=(V,E) je množina W⊂V taková, že v H−S jsou u,w v různých komponentách souvislosti U,W.
Věta Mengerova, vrcholová varianta, lokální příchuť Pro každý graf G=(V,E) a vrcholy u,w∈V,{u,w}∉E je pG(u,w)=cG(u,w).
Důkaz Nerovnost ≥ jde dokázat snadno. Dokážeme ≤ indukcí přes počet hran. Pro nula hran platí. Budeme speciálně uvažovat graf, kde pro všechna e∈E je |e∩{u,w}|=1. V takovém grafu triviálně platí cG(u,w)=pG(u,w)=|NG(u)∩NG(w)|. Teď uvažujme jiný graf a v něm nějakou hranu {a,b}=f∈E takovou, že f∩{u,w}=∅. Definujme H≔G−f,K≔cG(u,w). Potom k≥pG(u,w)≥pH(u,w)=IPcH(u,w)≥cG(u,w)−1=k−1. Z toho plyne cH(u,w)∈{k,k−1}. Pokud to je k, potom v první nerovnosti nastane rovnost, tedy platí tvrzení, které se snažíme dokázat. Předpokládejme pro spor, že cH(u,w)=k−1. Tedy existuje S⊂V,|S|=k−1 takové, že H−S je nesouvislý. Vezmeme čerstvý vrchol u¯ a definujeme nový graf Gu s V(Gu)≔V∖{u}∪{u¯},E(Gu)≔E∖{{u,v}|v∈G}∪{{u¯,b}}∪{{u¯,s}|s∈S}. TBD
Lemma Nechť G=(V,E) je neúplný graf. Potom
κ(G)=min{pG(u,v)|u,w∈V,{u,w}∉E}.
Důkaz Kdybychom uvažovali všechny dvojice u,w∈V, platilo by to z definice. Předpokládejme pro spor, že pro všechny u≠w takové, že pG(u,w)=κ(G), je {u,w}∈E. Pro taková x,y definujme H≔G−{x,y}. Podle lokální příchutě Mengera je cH(x,y)=pH(x,y)=pG(x,y)−1=κ(G)−1. TBD
Věta Mengerova, vrcholová varianta, globální příchuť Graf G=(V,E) je k-souvislý, právě když |V|≥k+1 a pro všechny W⊂V,|W|≤k−1 je podgraf indukovaný V∖W souvislý.
Důkaz Plyne z lokální verze a předchozího lemmatu.
Věta Přidáme-li ke k-souvislému grafu vrchol stupně k, výsledkem bude opět k-souvislý graf.
Důkaz Označme x nový vrchol a G+ nový graf. Stačí, aby pro |W|=k−1 byl G+−W souvislý graf. Je-li x∈W, potom G+−W≃G−(W∖{x}), což je souvislý. Pokud x∉W, potom G+−W≃(G−W)+x, kde G−W je souvislý a x je stupně alespoň 1, takže je k němu taky připojen.
Důsledek Je-li graf G=(V,E) k-souvislý a X,Y⊂V,|X|=|Y|=k, potom G obsahuje k vrcholově disjunktních cest z X do Y.
Důkaz Přidáme dva vrcholy, které spojíme jeden se všemi vrcholy z X a druhý s Y, a použijeme Mengera.
Důsledek Nechť G=(V,E) je k-souvislý graf, x∈V,Y⊂V∖{x},|Y|=k. Potom existuje k cest z x do Y, které jsou vrcholově disjunktní až na x.
Definice Nechť G=(V,EM) je multigraf a u,w∈V,u≠w. Potom p′(u,w) je maximální k takové, že existuje k hranově disjunktních cest z u do w. G je hranově k-souvislý, pokud pro všechna u,w∈V,u≠w je p′(u,w)≥k. κ′(G) je největší k takové, že G je hranově k-souvislý.
Definice Řez v multigrafu (G,EM) je množina F⊂EM taková, že comp(G−F)>comp(G).
Definice Nechť G=(V,EM) je multigraf a u,w∈V,u≠w. Potom c′(u,w) je minimální počet hran, které je nutné odstranit, aby neexistovala cesta z u do w.
Věta Mengerova, hranová verze, lokální příchuť Nechť G=(V,EM) je multigraf a u,w∈V,u≠w. Potom cG′(u,w)=pG′(u,w).
Důkaz Pozdéji.
Věta Mengerova, hranová verze, globální příchuť alias Fordova-Fulkersonova Nechť G=(V,EM) je multigraf, právě když pro každou F⊂EM,|F|≤k−1 je G−F souvislý.
Důkaz Triviálně plyne z lokální příchutě.
Definice Nechť G=(V,EM) je multigraf a X⊂V. Hranice X v G je
∂G(X)≔{e∈EM||e∩X|=1}.
Věta
cG′(u,w)=min{∂G(X)|{u}⊂X⊂V∖{w}}.

Digrafy

Definice Digraf je dvojice G≔(V,A), kde V je konečná množina vrcholů a A⊂V2∖{(v,v)|v∈V} jsou šipky.
Definice Orientovaný graf je trojice G=(V,E,o), kde (V,E) je graf a o:E→V je funkce taková, že ∀e∈E:o(e)∈e.
Poznámka Orientovaný hraf můžeme chápat jako digraf bez obousměrných šipek. Pro (u,v)∈A vezmeme o({u,v})≔v.
Definice Turnaj je orientovaný úplný graf.
Definice Orientovaná cesta v digrafu (V,A) je posloupnost u0a1u1a2⋯akuk taková, že ui∈V,ai∈A, ai=(ui−1,ui) a ui≠uj pro i≠j.
Definice Orientovaná kružnice je orientovana cesta s přidanou hranou z koncového do počátečního vrcholu.
Poznámka Orientovaná kružnice na rozdíl od neorientované může mít délku 2 (ale ne v orientovaném grafu).
Definice Digraf je acyklický, pokud neobsahuje kružnici jako podgraf.
Definice Orientovaná hranice v digrafu G=(V,A) je
δ+(X)≔{(a,b)∈A|a∈X∧b∉X},
δ−(X)≔{(a,b)∈A|a∉X∧b∈X}.
Lemma Nechť D=(V,A) je digraf a s,t∈V. Potom nastane právě jedna z možností:
Důkaz Definujme X≔{x∈V|s⇝Dx}. Pokud t∈X, platí první možnost. Pokud t∉X, platí druhá možnost.

Toky v síti

Definice Tok v digrafu z vrcholu s do vrcholu t je funkce φ:E→ℕ0 taková, že pro všechna w∈V∖{s,t} platí Kirchoffův zákon:
∑e∈∂−(w)φ(e)=∑e∈∂+(w)φ(e).
Hodnota toku je val(φ)≔∑e∈∂+(s)φ(e)−∑e∈∂−(s)φ(e). Nosič toku je supp(φ)≔{e∈A|φ(e)>0}.
Lemma Je-li φ tok v digrafu G=(V,A), potom existuje tok φ′ v G se stejnou hodnotou, jehož nosič je acyklický faktor G.
Důkaz Pokud suppφ neobsahuje cyklus, jsme hotovi. Jinak označme ε≔minφ(e*), kde e* jede přes šipky cyklu. Potom ze všech hran cyklu odečteme ε. Budeme opakovat, až vznikne acyklický faktor. Jelikož při každém kroku zmizí alespoň jedna hrana, algoritmus musí někdy skončit.
Lemma Nechť D=(V,A) je digraf, φ je tok z s∈V do t∈V a X⊂V,s∈X,t∉X. Potom
val(φ)=∑e∈∂+(X)φ(e)−∑e∈∂−(X)φ(e).
Důkaz Jednoduše plyne z definice hodnoty a z Kirchoffa.
Definice Kapacita hran digrafu G=(V,A) je funkce c:E→ℕ0. Tok φ je c-přípustný, pokud ∀e∈A:φ(e)≤c(e).
Definice Síť je pětice (V,A,s,t,c), kde (V,A) je digraf, s,t∈V a c je kapacita.
Věta Nechť D=(V,A) je digraf a φ je tok z s∈V do t∈V s hodnotou k≔val(φ). Potom existují orientovaný cesty P1,…,Pk z s do t takové, že každá hrana e je obsažena v nejvýše φ(e) cestách.
Důkaz Indukcí přes k. Pro k=0 triviální. Jistě existuje nějaká cesta z s do t – kdyby neexistovala, potom by existovala množina [s]⊂X⊂V∖{t} s ∂+(X)=∅, což je ve sporu s předchozím lemmatem.