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 hran, 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.
Definice Nechť φ je tok v síti (V,A,s,t,c). Neorientovaná cesta P=(s=v0,e1,…,vl=t) je φ-zlepšující cesta, pokud pro každou hranu ei platí:
Lemma Existuje-li k c-přípustnému toku φ v síti zlepšující cesta P, potom existuje c-přípustný tok ψ s val(ψ)=val(φ)+1.
Důkaz Vezmeme
ψ(e)≔{φ(e)e∉P,φ(e)+1e∈Ppo směru,φ(e)−1e∈Pproti směru.
Definice Nechť (V,A,s,t,c) je síť. Kapacita množiny {s}⊂X⊂V∖{t} je
cap(X)≔∑e∈∂G+(X)c(e).
Věta Fordova-Fulkersonova Nechť Φ je množina všech přípustných toků v síti (V,A,s,t,c). Potom
maxφ∈Φval(φ)=min{s}⊂X⊂V∖{t}cap(X).
Definice Tok je booleovský, pokud jeho obor hodnot je {0,1}.

Párování v grafu

Definice Nechť G=(V,E) je graf. Množina M⊂E je párování v G, pokud každé dvě hrany jsou disjunktní. Největší možnou velikost párování označíme ν(G).
Definice Nechť G=(V,E) je graf. Množina X⊂V je vrcholové pokrytí v G, pokud každá hrana obsahuje alespoň jeden vrchol z X. Nejmenší možnou velikost vrcholového pokrytí označíme τ(G).
Věta Pro každý graf G je ν(G)≤τ(G)≤2ν(G).
Důkaz Máme-li vrcholové pokrytí velikosti τ(G), potom každá hrana nějakého párování musí obsahovat alespoň jeden vrchol z pokrytí, takže jich nemůže být víc. Naopak máme-li párování velikosti ν(G), potom sjednocení konců všech jeho hran je pokrytí – kdyby nebylo, existovala by hrana, kterou bychom do párování mohli přidat, takže by nebylo maximální.
Definice Nechť M je párování v grafu G. Cesta v G je M-střídavá, pokud se v ní střídají hrany v M a mimo M. M-střídavá cesta je M-zlepšující, pokud její počáteční a koncový vrchol neleží v žádné hraně M.
Lemma Bergeovo Párování M je maximální, právě když neexistuje M-zlepšující cesta.
Věta Königova Je-li graf G bipartitní, potom τ(G)=ν(G).
Důkaz Stačí ukázat ≤. Nechť A,B jsou partity G a M je největší párování v G. Označme
AM≔A∩⋃M,Bm≔B∩⋃M,AZ≔A∖AM,BZ≔B∖BM,
AX≔{a∈AM|existujeM-střídavá cesta zx∈AZdoA},
BX≔{b∈BM|∃a∈AX:{a,b}∈M},
AY≔AM∖AX,BY≔BM∖BX,X≔BX∪AY.
Zjevně |X|=|M|. Stačí dokázat, že X je vrcholové pokrytí. Nějak dokážeme, že neexistuje žádná hrana z AZ do BZ, z AZ do BY, z BZ do AX nebo z AX do BY. Z toho už plyne, že každá hrana jde z AX nebo z BY.
Definice Nechť G=(V,E) je graf. Sousedství množiny S⊂V je NG(S)≔⋃x∈SNG(x).
Definice Párování M v grafu G=(V,E) je perfektní, pokud |M|=|V|2.
Věta Hallova Nechť G je bipartitní graf s partitami A,B. Potom ν(G)=|A|, právě když ∀S⊂A:|NG(S)|≥S.
Důkaz
(⇒)
Triviální.
(⇐)
Jistě τ(G)≤|A|. Dokážeme opačnou nerovnost, potom už z Königovy věty bude plynout požadovaná rovnost. Pro dané vrcholové pokrytí X označme A′≔A∖X. Potom NG(A′)⊂B∩X, takže
|A|=|A∩X|+|A′|≤|A∩X|+|NG(A′)|≤|A∩X|+|B∩X|=|X|.
Důsledek Každý k-regulární bipartitní graf obsahuje perfektní párování.
Důsledek Hrany k-regulárního bipartitního grafu se dají rozložit na k disjunktních perfektních párování.
Definice Nechť G=(V,E) je graf. Připomeňme, že 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. Velikost největší nezávislé množiny označme α(G).
Věta Pro každý graf G=(V,E) platí α(G)+τ(G)=|V|.
Důkaz Je-li X pokrytí, potom V∖X je nezávislá množina. Naopak je-li I nezávislá množina, potom V∖I je vrcholové pokrytí.
Definice Nechť G=(V,E) je graf bez izolovaných vrcholů. Množina F⊂E je hranové pokrytí, pokud V=⋃F. Nejmenší možnou velikost hranového pokrytí značíme ρ(G).
Věta Gallaiova Pro každý graf G=(V,E) bez izolovaných vrcholů platí ν(G)+ρ(G)=|V|.
Důkaz Je-li M párování maximální velikosti, potom F≔M∪{ex|x∈V∖⋃M} je hranové pokrytí, kde ex je libovolná hrana obsahující x. Nechť naopak F je minimální hranové pokrytí. Potom H≔(V,F) je faktor s δ(H)≥1. V H jistě každá hrana obsahuje alespoň jeden vrchol stupně 1, z čehož speciálně plyne, že je acyklický. Z toho už je vidět, že vezmeme-li z každé komponenty souvislosti H libovolnou hranu, dostaneme tím párování kýžené velikosti.
Definice Je-li G graf, potom odd(G) je počet komponent souvislosti liché velikosti v G.
Definice Bariéra v grafu G=(V,E) je množina B⊂V takové, že odd(G−B)>|B|.
Věta Pokud v grafu existuje bariéra, potom v něm neexistuje perfektní párování.
Důkaz Jednoduchý.
Definice Je-li M párování v grafu G=(V,E), potom unmG(M)≔|G|−2|M|.
Lemma Nechť G=(V,E) je souvislý graf takový, že ∀v∈V:ν(G−v)=ν(G). Potom ν(G)=|V|−12.
Důkaz Indukcí podle d≔distG(u,w) dokážeme pro každé u,w∈V, že každé maximální párování M má alespoň jeden z u,w na konci nějaké své hrany. Pro d=1 triviální. Nechť pro spor d≥2 a existuje maximální párování M0 neobsahující u ani w. TBD
Věta Tutteova-Bergeova formule Pro každý graf G=(V,E) platí
maxB⊂Vodd(G−B)=minM⊂EpárováníunmG(M).
Důkaz Nerovnost ≤ je prý triviální. Dokážeme nerovnost ≥ indukcí přes |V|. Pro |V|=1 ízy pízy. Je-li |V|≥2, rozlišíme tři případy:
  • Je-li G nesouvislý, uplatníme indukční předpoklad na každou komponentu souvislosti a vezmeme sjednocení obou získaných množin B.
  • Pokud G je souvislý a existuje vrchol v∈V takový, že ν(G−v)<ν(G), uplatníme indukční předpoklad na G−v. K získané B přidáme v.
  • Pokud G je souvislý a neexistuje takový vrchol, stačí použít lemma.
Důsledek Tutte Graf má perfektní párování, právě když ∀B⊂V:|B|≥odd(G−B) neboli neobsahuje bariéru.
Poznámka To už samozřejmě víme i bez toho.
Důsledek Pro každý graf G=(V,E) platí
ν(G)=minB⊂V|V|−odd(G−B)+|B|2.
Důsledek Petersen Každý 3-regulární graf bez mostů má perfektní párování.
Důkaz Nechť bez újmy na obecnosti G je souvislý. Pro libovolnou množinu B⊂V uvažujme souvislé komponenty G−B. Z každé takové komponenty, která má lichou velikost, musí vést do B aspoň tři hrany (jalikož neexistuje most a dvě to nemůžou být kvůli větě o potřesení rukou). Z toho plyne
3⋅odd(G−B)≤počet hran zBdoV−B≤3|B|
Tím jsme ověřili podmínku pro Tutteovu větu.

Hranová barevnost grafu

Definice Nechť k∈ℕ. Hranové k-obarvení multigrafu G=(V,EM) je funkce c:EM→[k] taková, že pro každé i∈[k] je c−1(i) párování. Hranová barevnost G je nejmenší k takové, že existuje hranové k-obarvení; značíme ji χ′(G).
Poznámka Zjevně χ′(G)≥Δ(G). Ovšem rovnost obecně neplatí, například χ′(C3)=3, ale Δ(C3)=2.
Věta Königova Je-li G=(V,EM) bipartitní multigraf, potom χ′(G)=Δ(G).
Důkaz Indukcí podle |EM|. Pro |EM|=0 triviální. Nechť e={u,w}∈EM,G′≔G−e. Je-li Δ(G′)<Δ(G), potom stačí použít indukční předpoklad a dát hraně e novou barvu. Pokud Δ(G′)=Δ(G), potom podle indukčního předpokladu existuje Δ(G)-obarvení c pro G′. Jelikož degG′(u),degG′(w)<Δ, jistě existuje barva α, kterou není obarvena žádná hrana z u, a barva β, kterou není obarvena žádná hrana z w. Pokud α=β, stačí obarvit e touto barvou. Jinak definujme Mα≔c−1(α),Mβ≔c−1(β). Potom Mα▵Mβ = Mα∪Mβ. Dále označme H≔(V,Mα▵Mβ). TBD
Věta Vizingova Pro každý graf G=(V,E) platí χ′(G)≤Δ(G)+1.
Poznámka Pro multigrafy věta neplatí. Vezmeme-li například „tlustý trojúhelník“, který má tři vrcholy a každé dva jsou spojené μ hranami, potom χ′(G)=3μ a Δ(G)=2μ.
Důsledek
χ′(Kn)={nnliché,n−1nsudé.
Důkaz Indukcí přes počet hran. Pro 0 hran nebo 1 hranu triviální. Nechť pro nějakou hranu e={x,y} je G′≔G−e. Podle indukčního předpokladu pro tento podgraf existuje obarvení c. Pro každý v∈V definujme množinu nepoužitých barev
F(v)≔{α∈[Δ+1]|v∉⋃c−1(α)}.
Jelikož Δ je maximální stupeň, pro všechny v∈V je |F(v)|≥1 a speciálně pro x,y je to ≥2. Nechť pro spor G nelze obarvit Δ+1 barvami, takže F(x)∩F(y)=∅. Na NG(y) definujeme pomocný digraf H, kde (u,v)∈E(H), pokud c({u,y})∈F(v). Speciálně degH+(x)=0, protože hrana {x,y} žádnou barvu nemá. Zároveň podle předpokladu je degH−(x)≥|F(x)|≥2. Dále definujme
Z≔{z∈NG(y)|z⇝Hx}.
Podgraf H indukovaný touto množinou označíme H. Cílem bude dokázat, že pro všechna z∈Z je degH′+(z)≤1 a degH′−(z)≥1, což bude spor. Začneme tím, že dokážeme
∀z∈Z:F(z)∩F(y)=∅.
Nechť pro spor pro nějaké z0∈Z existuje nějaká barva α∈F(z)∩F(y). Jelikož z∈Z, jistě v H existuje nějaká orientovaná cesta z0→z1→⋯→zk=x. Přebarvíme hrany následovně:
c~({z0,y})≔α,c~({z1,y})≔c({z0,y}),…,c~({zk,y})≔c({zk−1,y}).
Tím jsme našli platné obarvení obarvující i hranu {zk,y}=e, což je spor. Dále dokážeme
∀z0∈Z,∀α∈F(z),∀β∈F(y):z0→α⋅→β⋅→α⋅→β⋯→αy.
Nechť pro spor existují z0,α,β takové, že žádná taková cesta neexistuje. Mezi všemi takovými z0 vezměme takové, že distH′(z0,x) je minimální. Jistě v H′ existuje nějaká cesta z0→z1→⋯→x. Půjdeme v G′ ze z0 střídavě po hranách barev α,β a skončíme ve chvíli, kdy už to v nějakém vrcholu q nepůjde. Nějak snadno dokážeme, že q≠zi pro žádné i. Něco něco něco. A ze dvou tvrzení, která jsme dokázali, plyne přesně to, co jsme chtěli.
Definice Pro multigraf G označme μ(G) nejvyšší násobnost hrany.
Věta Vizingova⁺ Pro každý multigraf G=(V,E) platí χ′(G)≤Δ(G)+μ(G).
Důkaz Domácí úkol.
Věta Shannonova Pro multigraf G platí
χ′(G)≤⌊32μ(G)⌋.

Vrcholová barevnost grafu

Definice Nechť k∈ℕ. Vrcholové k-obarvení grafu G=(V,E) je funkce c:V→[k] taková, že pro každé i∈[k] je c−1(i) nezávislá množina. Vrcholová barevnost G je nejmenší k takové, že existuje hranové k-obarvení; značíme ji χ(G).
Poznámka Bipartitní graf můžeme ekvivalentně definovat jako 2-obarvitelný.
Věta Pro každý graf G je χ(G)≤Δ(G)+1.
Důkaz Budeme postupně přidávat vrcholy a vždy máme nanejvýš Δ(G) barev, které nesmíme použít.
Definice Hranograf multigrafu G=(V,EM) je graf L(G)=(EM,F), kde vrcholy jsou spojené hranou, pokud jako hrany původního grafu mají společný vrchol.
Věta Pro každý multigraf G je χ′(G)=χ(L(G)).
Důkaz Triviální.
Definice Nechť d∈ℕ0. Graf G=(V,E) je d-degenerovaný, pokud je nulový nebo existuje v∈V takový, že deg(v)≤d a G−v je d-degenerovaný.
Věta Pro d-degenerovaný graf G je χ(G)≤d+1.
Důkaz Triviální.
Definice Klika v grafu G=(V,E) je množina W⊂V taková, že podgraf indukovaný W je úplný. Velikost největší kliky v grafu značíme ω(G).
Poznámka Klika v grafu je nezávislá množina v jeho doplňku. Tedy speciálně ω(G)=α(G¯).
Věta Pro každý graf G je χ(G)≥ω(G).
Důkaz Triviální.
Věta Pro každý graf G=(V,E) je χ(G)+χ(G¯)≤|V|+1.
Důkaz Indukcí před |V|. Pro |V|=0 triviální. Nechť x∈V,H≔G−x. Podle indukčního předpokladu obarvíme H pomocí k barev a H¯ pomocí k¯ barev, kde k+k¯≤|V|. TBD
Věta Brooksova Pro neúplný souvislý graf G s Δ(G)≥3 platí χ(G)≤Δ.
Důsledek Je-li G souvislý graf splňující χ(G)=Δ(G)+1, potom je buď úplný, nebo cyklus.
Definice Nechť k∈ℕ. Graf G je k-kritický, pokud χ(G)=k a pro všechny podgrafy H je χ(H)<k.
Věta Každý graf G s χ(G)≥k obsahuje k-kritický podgraf.
Důkaz Triviální.
Věta Je-li graf k-kritický, potom je souvislý.
Důkaz Triviální.
Věta Je-li graf G k-kritický, potom δ(G)≥k−1.
Důkaz Triviální.
Věta Obsahuje-li graf kliku jako řez, potom není k-kritický.
Věta Mycelského Pro každé k≥2 existuje graf Gk takový, že χ(Gk)=k a ω(Gk)=2.
Důkaz Indukcí. Pro k=2 vezmeme P2. Pro k≥3 vezmeme graf Gk−1. Vedle položíme jeho kopii, jejíž vrcholy nebudou propojené mezi sebou, ale každý bude propojen s odpovídajícími vrcholy původního grafu. Poté ještě přidáme jeden vrchol, který propojíme se všemi „naklonovanými“ vrcholy. Tím jsme vytvořili Gk.

Pravděpodobnostní metoda

Budeme uvažovat diskrétní pravděpodobnostní prostor (Ω,2Ω,p),p:Ω→[0,1], kde P(A)≔∑a∈Ap(a) a P(Ω)=1. Jako syntaktickou zkratku budeme používat značení ℙ[⋯], kde v hranatých závorkách může být elementární jev, jev nebo výrok.
Poznámka Nechť Gn je náhodný n-vrcholový graf a 𝒫︀ je nějaká jeho vlastnost. Pokud ℙ[𝒫︀(Gn)]>0, potom existuje graf, který má vlastnost 𝒫︀.
Poznámka Je-li X celočíselná nezáporná náhodná veličina a 𝔼X<1, potom ∃ω∈Ω:X(ω)=0.
Poznámka Je-li X náhodná veličina a 𝔼X≥t, potom ∃ω∈Ω:X(ω)≥t.
Věta Markovova nerovnost Nechť X je nezáporná náhodná veličina a t≥0. Potom ℙ[X≥t]≤𝔼[X]t.
Důkaz
𝔼[X]=∑i∈X(Ω)ℙ[X=i]⋅i≥∑i≥tℙ[X=i]⋅i≥t⋅∑i≥tℙ[X=i]=t⋅ℙ[X≥t].
Pomocí pravděpodobnosti můžeme dokazovat tvrzení, která vůbec s pravděpodobností nesouvisí.
Věta Každý graf G=(V,E) obsahuje bipartitní faktor (V,F) s |F|≥|E|2.
Důkaz Pro každý vrchol se rovnoměrně náhodně rozhodneme, jestli bude v partitě A nebo B. Nechť X je náhodná veličina reprezentující počet hran mezi partitami. Stačí dokázat, že 𝔼X≥|E|2. Pro každou hranu definujme náhodnou veličinu Xe, která bude 1, pokud vede mezi partitami, jinak 0. Potom zjevně 𝔼Xe=12. Z toho máme
𝔼X=𝔼∑e∈EXe=∑e∈E𝔼Xe=|E|2.
Definice Nechť G=(V,E) je graf. Množina W⊂V je dominující v G, pokud ∀x∈V∖W:NG(x)∩W≠∅. Nejmwnší možnou velikost dominující množiny značíme γ(G).
Věta Má-li graf G=(V,E) minimální stupeň δ, potom
γ(G)≤|V|⋅1+ln(δ+1)δ+1.
Důkaz Pro dané p∈[0,1] uvažujme náhodnou podmnožinu Xp⊂V, kde pro každý vrchol x∈V je ℙ[x∈Xp]=p. Zjevně 𝔼|Xp|=p⋅|V|. Dále vezměme náhodnou množinu Yp≔{y∈V∖Xp|NG(y)∩Xp=∅} neboli vrcholy, kvůli kterým Xp není dominující množina. Potom jistě Xp⊎Yp je dominující množina. Jelikož množiny Xp,Yp jsou disjunktní, máme 𝔼|Xp⊎Yp|=𝔼|Xp|+𝔼|Yp|. Spočteme si
𝔼|Yp|=∑y∈Vℙ[y∈Yp]=∑y∈V(1−p)1+degG(p)≤|V|⋅(1−p)1+δ≤|V|⋅exp(−p⋅(1+δ)).
Vezmeme-li speciálně p≔ln(δ+1)δ+1, potom
p+exp(−p⋅(1+δ))=1+ln(δ+1)δ+1.
Z toho už plyne tvrzení věty.
Věta Erdősova Pro všechna k,g≥3 existuje graf Gk,g takový, že χ(Gk,g)≥k a neobsahuje cykly délky ≤g.
Důkaz Místo χ(Gk,g)≥k ukážeme silnější tvrzení α(Gk,g)≤|V(Gk,g)|k. Pro dané N∈ℕ,p∈(0,1) definujme náhodný graf G0=([N],E0), kde pro každou e∈([N]2) je ℙ[e∈E0]=p. Pro libovolnou množinu S⊂[N] je
P[Snezávislá vG]=(1−p)(|S|2)≤exp(−p⋅(|S|2))≤exp(−p⋅(|S|−1)22).
Definujme náhodnou veličinu Xs jako počet nezávislých množin velikosti s v G0. Potom
𝔼Xs=(Ns)⋅exp(−p⋅(|S|−1)22)≤(e⋅Ns−1)s⋅exp(−p⋅(|S|−1)22).
Zvolme t≔N2k. Stačí dokázat 𝔼Xt+1<12. Z Markovovy věty potom plyne
ℙ[Xt+1≥1]<12∴ℙ[Xt+1=0]>12∴ℙ[α(G0)≤t]>12.
Odhadujme
𝔼Xt+1=(2ek)N2k+1⋅exp(−pN28k2)≤🪄 magie 🪄<12.
Zatím jsme neřekli nic o cyklech. Označíme-li Yl počet cyklů délky l, potom
𝔼Yl=(Nl)⋅(l−1)!2⋅pl≤(N⋅p)l=(16k2)l,
∑l=3gYl≤∑l=3g(162)l≤Cg,k
pro nějakou konstantu Cg,k. TBD

Ramseyova teorie

Příklad V grafu se šesti vrcholy vždy existuje klika velikosti 3 nebo nezávislá množina velikosti 3.
Důkaz Uvažujme nějaký vrchol u. Určitě platí jedna ze dvou možností:
  • u je spojen alespoň se třemi dalšími vrcholy. Pokud jsou nějaké z nich spojené, potom máme trojúhelník, jinak máme antitrojúhelník.
  • u je nespojen alespoň se třemi dalšími vrcholy. Pokud jsou nějaké z nich nespojené, potom máme antitrojúhelník, jinak máme trojúhelník.
Věta Ramseyova Nechť k,ℓ∈ℕ a G je graf s alespoň (k+ℓ−2k−1) vrcholy. Potom ω(G)≥ℓ∨α(G)≥k.
Důkaz Indukcí podle k+ℓ. Pro k=1 nebo ℓ=1 triviálně platí. Nechť k,ℓ≥2. Uvažujme vrchol v v grafu s alespoň (k+ℓ−2k−1)=(k+ℓ−2ℓ−1) vrcholy.
  • Pokud degG(v)≥(k+ℓ−3k−1), potom podle indukčního předpokladu podgraf indukovaný NG(v) obsahuje kliku velikosti ℓ−1 nebo nezávislou množinu velikosti k.
  • Pokud degG¯(v)≥(k+ℓ−3ℓ−1), potom podle indukčního předpokladu podgraf indukovaný NG¯(v) obsahuje kliku velikosti ℓ nebo nezávislou množinu velikosti k−1.
  • Jiná možnost nastat nemůže, což plyne ze vzorce pro součet binomických čísel.
Definice Ramseyovo číslo R(k) pro k∈ℕ je nejmenší číslo takové, že každý graf s R(k) vrcholy splňuje max{ω(G),α(G)}≥k.
Poznámka Podle předchozí věty nějaké takové číslo existuje.
Poznámka Ekvivalentně je to nejmenší takové číslo, že každé hranové obarvení KR(k) dvěma barvami obsahuje jednobarevnou kliku.
Důsledek Pro každá k,r∈ℕ existuje n∈ℕ takové, že každé r-obarvení Kn obsahuje monochromatickou barvu.
Důkaz Indukcí. Pro r=2 dokázáno. Je-li r≥3, seskupíme barvy rovnoměrně do dvou barev a najdeme graf, který obsahuje dostatečně velkou jednobarevnou kliku. Potom na ni použijeme indukční předpoklad.
Poznámka Známe R(3)=6,R(4)=18. Další Ramseyova čísla už přesně neznáme.
Věta Erdősova Pro každé k≥2 je R(k)≥2k2.
Důkaz Vezměme náhodný graf G s n≔⌈2k2⌉−1 vrcholy, kde každé dva jsou spojené hranou s pravděpodobností 12. Uvažujme náhodnou veličinu X jako počet klik nebo nezávislých množin velikosti k. Potom
𝔼X=(nk)⋅21−(k2)≤nkk!⋅21−(k2)≤2k22⋅21−(k⋅k−12)k!=2k2+1k!<1.
Věta Goodmanova Nechť c je hranové 2-obarvení Kn. Potom existuje alespoň n⋅(n−1)⋅(n−5)24 jednobarevných trojúhelníků.
Důkaz Nechť X je počet strakatých (nejednobarevných) trojúhelníků. V každém takovém trojúhelníků existují dva vrcholy s různobarevnými hranami. Označíme-li dv počet sousedů v s jednou konkrétní barvou, potom
2X=∑vdv⋅(n−1−dv).
Vyšetřením maxima dostaneme
X≤n2⋅(n−12)2.
Počet monochromatických trojúhelníků je potom (n3)−X, čímž dostaneme kýžený odhad.
Věta Turánova Pokud graf G=(V,E) neobsahuje kliku velikosti k+1, potom
|E|≤k−12k|V|2.
Poznámka Dá se vymyslet, že odhad už nejde vylepšit. Například tak, že člověk nakreslí čtyři sušenky propojené svazky laserových paprsků.
Důkaz Indukcí přes k. Pro k=1 triviální (pokud graf neobsahuje hrany, potom počet hran je nanejvýš 0). Pro dané fixní k≥2 použijeme indukci přes n≔|V|. Je-li n≤k, tvrzení snadno ověříme. Nechť n≥k+1. Bez újmy na obecnosti můžeme předpokládat, že ω(G)=k. Vezměme kliku velikosti k. Ve zbylých n−k vrcholech je podle indukčního předpokladu nanejvýš n−12k⋅(n−k)2 hran. Mezi klikou a neklikou vede nanejvýš (k−1)⋅(n−k) hran, protože podle předpokladu není žádný vrchol nekliky spojený se všemi vrcholy kliky. Celkový počet hran je tedy nanejvýš
(k2)+(k−1)⋅(n−k)+k−12k⋅(n−k)2=k−12⋅(k+2n−2k+n2−2kn+k2k)=k−12⋅n2k.
Lemma Pro graf G=(V,E) platí
∑v∈VdegG(v)2≥4|E|2|V|.
Důkaz Vezmeme vektory u≔(degG(v1),…,degG(vn)),v≔(1,…,1) a na jejich skalární součin aplikujeme Cauchy-Schwarzovu nerovnost a větu o potřesení rukou.
Věta Erdősova Neobsahuje-li graf G=(V,E) podgraf C4, potom
|E|≤|V|⋅(1+4|V|+1)4.
Důkaz Spočtěme X≔ počet trojic u,x,w∈V takových, že {u,x},{x,w}∈E. Jelikož G neobsahuje C4, pro každá u,w existuje nanejvýš jedno takové x, takže X≤(|V|2). Zároveň s použitím lemmatu
X=∑x∈V(degG(x)2)=(∑x∈VdegG(x)22)−|E|≥2|E|2|V|−|E|.
Čachrami a machrami dostaneme
|V|3+2|V||E|−4|E|2≥0.
Vyšetřením extrému v závislosti na |E| získáme požadovaný odhad.
Věta Pro každé p∈ℙ existuje graf bez C4 s p2−1 vrcholy a přibližně p32 hranami.
Důkaz Vezměme V≔ℤp×ℤp∖{(0,0)} a E≔{{(a,b),(x,y)}|ax+by=1}. Důkaz, že to bude fungovat, je ponechán jako cvičení pro čtenáře.
Věta Jensenova nerovnost Nechť X je náhodná proměnná a f je konvexní funkce. Potom 𝔼f(X)≥f(𝔼X).
Důsledek Je-li f konvexní a x1,…,xn∈ℝ, potom
1n∑i=1nf(xi)≥f(1n∑i=1nxi).
Poznámka Pro k∈ℕ definujme gk(x)≔[x>k−1]⋅(xk). Potom gk je konvexní.
Věta Kővári, Sós, Turán Neobsahuje-li graf G=(V,E) podgraf Ks,t pro s≤t, potom
|E|≤(ts+s)⋅|V|2−1s.
Důkaz Podobný jako u Erdősovy věty, ale s využitím Jensenovy nerovnosti.

Rovinné grafy

Definice Topologická kružnice v rovině je spojitá funkce k:[0,1]→ℝ2 prostá na [0,1) a splňující k(0)=k(1).
Věta Jordanova věta o křivce Každá topologická kružnice v rovině rozděluje rovinu na dvě souvislé oblasti.
Definice Nakreslení grafu G=(V,E) je (g,(fe)E), kde g:V→ℝ2 je prostá funkce, pro každé e∈E je fE:[0,1]→ℝ2 prostá spojitá funkce a pro každou hranu e∈E platí
{fe(0),fe(1)}=g(e)∧fe((0,1))∩g(V)=∅.
Nakreslení je rovinné, pokud pro všechny e1,e2∈E je fe1((0,1))∩fe2((0,1))=∅.
Definice Graf je rovinný, pokud pro něj existuje nakreslení (g,(fe)E). Potom (G,g,(fe)E) je topologický rovinný graf. Značíme G.
Definice Nechť G=(G,g,(fe)E) je topologický rovinný graf. Označme X≔g(v)∪⋃e∈Efe([0,1]). Potom souvislé komponenty ℝ2∖X jsou stěny G. Neomezenou stěnu (která existuje právě jedna) nazýváme vnější stěna a značíme extG.
Definice Nechť G=(G,g,(fe)E) a F je stěna G. Potom ∂F je multimnožína všech hran G nakreslených na hranici F, přičemž je-li hrana most, potom ji počítáme dvakrát.
Věta Nechť G=(G,g,(fe)E) a F je stěna G. Potom existuje topologický rovinný graf (G,g′,(fe′)E) takový, jehož vnější stěna má hranici rovnou ∂F.
Důkaz Vůči vybrané stěně provedeme kruhovou inverzi. Alternativně, provedeme stereografickou projecki na kouli, otočíme ji tak, aby severní pól byl uvnitř vybrané stěny, a provedeme stereografickou projekci zpátky do roviny.
Příklad Grafy Kn pro n≤4 jsou rovinné.
Věta Graf K5 není rovinný.
Důkaz Nechť pro spor existuje nakreslení (g,(fe)E). Potom f{1,2}([0,1]),f{2,3}([0,1]),f{3,1}([0,1]) je topologická kružnice. Nechť bez újmy na obecnosti g(4) leží uvnitř této kružnice. Hrany od 4 do 1,2,3 ji rozdělují na tři části, tedy máme celkem čtyři části. Až už dáme 5 kamkoliv, s něčím nepůjde spojit.
Věta Eulerův vzorec Nechť G=(V,E) je rovinný graf a s je počet stěn v nějakém jeho nakreslení. Potom
|V|−|E|+s=1+comp(G).
Důkaz Později.
Důsledek Je-li G=(V,E) rovinný graf s |V|≥3, potom |E|≤3|V|−6. Pokud navíc G neobsahuje trojúhelník, potom |E|≤2|V|−4.
Důkaz Bez újmy na obecnosti můžeme předpokládat, že G je souvislý. Označme c počet dvojic (e,F), kde F je stěna s hranou e na hranici. Zjevně c=2|E|. Zároveň každá stěna má na hranici aspoň tři hrany (pokud mosty počítáme dvakrát), takže c≥3⋅s. Nyní stačí použít Eulerovu formuli. Pro případ bez trojúhelníků máme alespoň čtyři hrany místo alespoň tří.
Důsledek Grafy K5 a K3,3 nejsou rovinné.