Páros gráfok és síkbarajzolhatóság

Tétel — páros gráfok jellemzési tétele, 1. változat

Legyen \(G\) gráf, \(|V(G)| \ge 2\). Ekkor \(G\) páros gráf \(\iff\) \(G\) minden köre páros hosszú.

Bizonyítás

I. eset — ha \(G\) összefüggő: mivel \(G\) összefüggő, ezért van benne \(T\) feszítőfa. \(T\) páros gráf (fa lévén nincs benne kör), azaz létezik \(A, B\) csúcsosztály, amelyek megfelelőek \(T\)-re (bármely \(T\)-beli él egyik végpontja \(A\)-beli, a másik \(B\)-beli).

Most belátjuk, hogy \(A, B\) megfelelőek a \(T\)-n kívüli élekre is. Legyen \(e \in E(G) \setminus E(T)\). Mivel \(T\) fa, így \(T\) maximálisan körmentes \(\implies T + e\) tartalmaz egy kört. A feltétel szerint ez a kör páros hosszú. Mivel a kör tartalmazza az \(e\) élt (\(e\) nélkül \(T\) körmentes), de a többi éle \(T\)-beli, így a körbeli szomszédos csúcsok felváltva \(A\)- és \(B\)-beliek. A páros hossz miatt az \(e\) él két végpontja különböző osztályba kell essen (egyik \(\in A\), másik \(\in B\)). Tehát \(A\) és \(B\) jó csúcsosztályok \(G\)-re is \(\implies G\) páros gráf.

II. eset — ha \(G\) nem összefüggő:

1. Ha \(G\) üres gráf \(\implies G\) páros gráf.
2. Ha \(G\) nem üres gráf \(\implies\) a komponensei közt van legalább egy olyan, amely legalább 2 csúcsú. Ezek az I. eset szerint páros gráfok. Legyen \(A\): ezen komponensek 1. csúcsosztályainak uniója kiegészítve az izolált csúcsokkal; legyen \(B\): ezen komponensek 2. csúcsosztályainak uniója. Ezek megfelelő csúcsosztályok.

Tétel — páros gráfok jellemzési tétele, 2. változat

Legyen \(G\) gráf, \(|V(G)| \ge 2\). Ekkor \(G\) páros gráf \(\iff\) \(G\)-ben nincs páratlan hosszú kör.

Bizonyítás

Ez közvetlen következménye az 1. változatnak, hiszen "minden kör páros hosszú" pontosan ugyanazt jelenti, mint hogy "nincs páratlan hosszú kör".

Tétel — páros gráfok jellemzési tétele, 3. változat

Legyen \(G\) gráf, \(|V(G)| \ge 2\). Ekkor \(G\) páros gráf \(\iff\) \(G\)-ben minden zárt séta páros hosszú.

Bizonyítás

⟹: ugyanúgy bizonyítható, mint az 1. változatnál.

⟸: \(\forall\) zárt séta páros hosszú \(\implies \forall\) kör páros hosszú \(\xrightarrow{\text{1. változat}} G\) páros gráf.

Emlékeztető

Minden kör egyben zárt séta is, de nem minden zárt séta kör (a zárt séta ismételhet csúcsokat és éleket). Páros gráfban nincs páratlan hosszúságú kör!

Definíció — teljes páros gráf

Egy \(G\) páros gráfot \(A, B\) csúcsosztályokkal teljes páros gráfnak nevezünk, ha \(G\) egyszerű, és \(A\) minden csúcsa össze van kötve \(B\) minden csúcsával. Jelölés: \(|A|=m, |B|=n\) esetén \(K_{m,n}\).

Állítás

A \(K_{m,n}\) teljes páros gráf éleinek száma: \(|E(K_{m,n})| = m \cdot n\).

Tétel

Ha \(G\) egy \(n\) csúcsú egyszerű páros gráf, akkor:

\[ |E(G)| \le \left\lfloor \frac{n^2}{4} \right\rfloor \]

Bizonyítás

Legyen a két csúcsosztály mérete \(a = |A|\) és \(b = |B|\), ahol \(a + b = n\). A legtöbb élt akkor kapjuk, ha \(G\) teljes páros gráf, azaz \(|E(G)| \le a \cdot b = a(n - a)\). Az \(f(a) = a(n - a) = an - a^2\) másodfokú függvény maximuma ott van, ahol \(a = \frac{n}{2}\).

• Ha \(n\) páros: \(a = b = \frac{n}{2} \implies |E(G)| \le \frac{n}{2} \cdot \frac{n}{2} = \frac{n^2}{4}\).
• Ha \(n\) páratlan: \(a = \frac{n-1}{2}\) és \(b = \frac{n+1}{2} \implies |E(G)| \le \frac{n-1}{2} \cdot \frac{n+1}{2} = \frac{n^2 - 1}{4} = \left\lfloor \frac{n^2}{4} \right\rfloor\).

Eredet

3 ház – 3 kút probléma (\(K_{3,3}\)). Van 3 ház és 3 kút. Vezessünk minden háztól minden kútig ösvényt úgy, hogy az ösvények nem keresztezik egymást.

Definíció — síkbarajzolt gráf

• \(G\) csúcsai: síkbeli pontok,
• \(G\) élei: síkbeli görbék, amelyek nem metszik önmagukat, illetve nem mennek át csúcson,
• egy él gráfelméleti végpontjai: geometriai végpontjai,
• élek nem keresztezhetik egymást!

Definíció

• Egy \(G\) gráf síkbarajzolható gráf, ha izomorf egy síkbarajzolt gráffal.
• Hasonlóan definiálhatók térberajzolt gráfok térbeli pontokkal és görbékkel.
• Egy \(G\) gráf térberajzolható gráf, ha izomorf egy térberajzolt gráffal.

Emlékeztető

Síkbarajzolt = már le van rajzolva a síkba élek kereszteződése nélkül. Síkbarajzolható = le lehet rajzolni a síkba élek kereszteződése nélkül (létezik síkbarajzolt reprezentációja).

Tétel

Minden gráf térberajzolható.

Bizonyítás

Legyen \(G\) egy tetszőleges gráf. Vegyünk egy térbeli egyenest (\(e\)), és azon \(|V(G)|\) db pontot. Továbbá vegyünk \(|E(G)|\) db félsíkot, melyek határoló egyenese \(e\). Ha \(G\)-ben a \(k\)-adik él köti össze az \(i\)-edik és \(j\)-edik csúcsokat, akkor a \(k\)-adik félsíkon rajzoljunk görbét az \(i\)-edik és \(j\)-edik pontok közé úgy, hogy annak a végpontjain kívül ne legyen közös pontja az egyenessel. Az így kapott gráf egy térberajzolt gráf \(\cong G\).

Definíció — tartományok

Legyen \(G\) síkbarajzolt gráf. Jelölje \(X\) azon síkbeli pontok halmazát, melyek nem csúcsok és nem megy át rajtuk él. Két \(X\)-beli pont álljon relációban, ha van köztük \(X\)-ben haladó görbe. Ez a reláció ekvivalenciareláció, melynek ekvivalenciaosztályait \(G\) tartományainak nevezzük.

Definíció — duális gráf

Legyen \(G\) síkbarajzolt gráf. A \(G\) duális gráfja a \(G^*\) gráf, melyre:

• \(G^*\) csúcsai: \(G\) tartományai,
• \(G^*\) élei: \(G\) élei,
• egy él két végpontja \(G^*\)-ban: az él két oldalán lévő tartományok.

Tétel

Ha \(G\) síkbarajzolt gráf, akkor \(G^*\) síkbarajzolható.

Bizonyítás

Vegyünk fel \(G\) minden tartományának belsejében egy-egy pontot (a tartomány "fővárosát"). Ebből a pontból a tartományt határoló élek mindegyikéhez vezessünk csillagszerűen egymást nem metsző görbéket. Egy élt a két oldalról elérő görbék egyesítése után kapunk egy síkbarajzolt gráfot \(\cong G^*\).

Emlékeztető

Izomorf síkbarajzolt gráfok duálisai NEM feltétlenül izomorfak! A duális gráf szerkezete függ a síkbeli lerajzolás módjától is.

Tétel — kézfogási tétel síkbarajzolt gráfokra

Ha \(G\) síkbarajzolt gráf, akkor a tartományokat határoló élek számának összege \(= 2|E(G)|\).

Tétel — Euler-formula összefüggő gráfokra

Ha \(G\) összefüggő síkbarajzolt gráf, akkor:

\[ |V(G)| - |E(G)| + t(G) = 2 \]

ahol \(t(G)\) a tartományok száma.

Tétel — Euler-formula, általános változat

Ha \(G\) tetszőleges síkbarajzolt gráf, akkor:

\[ |V(G)| - |E(G)| + t(G) = c(G) + 1 \]

ahol \(c(G)\) a komponensek száma.

Tétel — Platóni testek gráfjai

Legyen \(G\) összefüggő síkbarajzolt gráf, amely \(k\)-reguláris és minden tartományát \(l\) db él határolja (\(k, l \ge 3\)). Ekkor a lehetséges paraméterek kényszerűen \((k-2)(l-2) < 4\), aminek pontosan 5 megoldása van az egész számok körében — ezek a szabályos testek (Platóni testek) élgráfjai:

1. \(k=3, l=3 \implies |V|=4, |E|=6, t=4\) (Tetraéder)
2. \(k=3, l=4 \implies |V|=8, |E|=12, t=6\) (Kocka / Hexaéder)
3. \(k=4, l=3 \implies |V|=6, |E|=12, t=8\) (Oktaéder)
4. \(k=3, l=5 \implies |V|=20, |E|=30, t=12\) (Dodekaéder)
5. \(k=5, l=3 \implies |V|=12, |E|=30, t=20\) (Ikozaéder)

Emlékeztető — a Platóni testekhez

Kettős duálisok: a kocka duálisa az oktaéder, a dodekaéderé az ikozaéder, a tetraéderé önmaga (önduális). Élek száma megegyezik a duális pároknál: \(k\) és \(l\) szerepet cserél, \(|E|\) azonos marad, \(|V|\) és \(t\) felcserélődik.

Tétel

Legyen \(G\) egyszerű síkbarajzolható gráf, hogy \(|V(G)| \ge 3\). Ekkor:

\[ |E(G)| \le 3|V(G)| - 6 \]

Bizonyítás

Feltehető, hogy az élek száma \(|E(G)| \ge 2\) (ha \(|E|=0\) vagy \(1\), és \(|V| \ge 3\), az állítás triviálisan teljesül). Vegyünk egy \(G\)-vel izomorf síkbarajzolt gráfot. Itt minden tartományt legalább \(3\) él határol, mert \(1\) vagy \(2\) határoló él esetén hurokél vagy párhuzamos él lenne, de \(G\) egyszerű.

A kézfogási tétel síkbarajzolt gráfokra:

\[ 2 \cdot |E(G)| = \text{tartományokat határoló élek számának összege} \ge 3 \cdot t(G) \implies t(G) \le \frac{2}{3}|E(G)| \]

Az Euler-formula alapján (feltéve, hogy \(G\) összefüggő, így \(c(G)=1\)):

\[ |V(G)| - |E(G)| + t(G) = 2 \implies t(G) = 2 - |V(G)| + |E(G)| \]

Ezt behelyettesítve a fenti egyenlőtlenségbe:

\[ 2 - |V(G)| + |E(G)| \le \frac{2}{3}|E(G)| \implies 6 - 3|V(G)| + 3|E(G)| \le 2|E(G)| \implies |E(G)| \le 3|V(G)| - 6 \]

Tétel

Legyen \(G\) egyszerű síkbarajzolható páros gráf, hogy \(|V(G)| \ge 3\). Ekkor:

\[ |E(G)| \le 2|V(G)| - 4 \]

Bizonyítás

Ismét tfh. \(|E(G)| \ge 2\). Vegyünk egy \(G\)-vel izomorf síkbarajzolt gráfot. Síkbarajzolt gráf egy tartományát határoló élek egy vagy több zárt sétát alkotnak. De a páros gráfok jellemzési tételei miatt ezek hossza páros \(\implies\) minden tartományt páros sok él határol \(\implies\) minden tartományt legalább \(4\) él határol.

\[ 2 \cdot |E(G)| \ge 4 \cdot t(G) \implies t(G) \le \frac{1}{2}|E(G)| \]

Az Euler-formulából \(t(G) = 2 - |V(G)| + |E(G)|\):

\[ 2 - |V(G)| + |E(G)| \le \frac{1}{2}|E(G)| \implies 4 - 2|V(G)| + 2|E(G)| \le |E(G)| \implies |E(G)| \le 2|V(G)| - 4 \]

Tétel

Ha \(G\) egyszerű, síkbarajzolható gráf, akkor \(\delta(G) \le 5\) (ahol \(\delta(G)\) a minimális fokszám).

Bizonyítás

Indirekt: tfh. \(\delta(G) \ge 6 \implies \forall v \in V(G): d(v) \ge 6\). Ekkor a fokszámösszeg:

\[ \sum_{v \in V(G)} d(v) \ge 6|V(G)| \implies 2|E(G)| \ge 6|V(G)| \implies |E(G)| \ge 3|V(G)| \]

Másfelől a korábbi tétel alapján \(|E(G)| \le 3|V(G)| - 6\). Ez ellentmondás, hiszen \(3|V(G)| \le |E(G)| \le 3|V(G)| - 6\) nem lehetséges! Így \(\delta(G) \le 5\).

Emlékeztető

A \(\delta(G) \le 5\) állítás kulcsfontosságú az Ötszín-tétel indukciós lépéséhez (lásd a következő jegyzetben) — garanciát ad arra, hogy minden síkgráfban van legalább egy legfeljebb 5-fokú csúcs, amit elhagyhatunk.

Definíció — él felosztása

Legyen \(G = (V, E, \varphi)\) gráf és \(e \in E\), hogy \(\varphi(e) = \{v_1, v_2\}\) (\(e\) végpontjai \(v_1, v_2\)). Ekkor az \(e\) él felosztásával adódó gráf \(G' = (V', E', \varphi')\), ahol:

• \(V' = V \cup \{x\}\) (\(x \notin V\), eredetileg \(x\) nem csúcs),
• \(E' = (E \setminus \{e\}) \cup \{e_1, e_2\}\) (\(e_1, e_2 \notin E\)),
• \(\varphi'(f) = \varphi(f)\) ha \(f \in E \setminus \{e\}\); \(\varphi'(e_1) = \{v_1, x\}\); \(\varphi'(e_2) = \{v_2, x\}\).

Definíció — élek összevonása

Legyen \(G = (V, E, \varphi)\) gráf, \(x \in V : d(x) = 2\), és az \(x\)-re illeszkedő két él \(e_1, e_2 \in E\), hogy \(\varphi(e_1) = \{v_1, x\}, \varphi(e_2) = \{v_2, x\}\). Ekkor az \(e_1, e_2\) élek összevonásával adódó gráf \(G' = (V', E', \varphi')\), ahol:

• \(V' = V \setminus \{x\}\),
• \(E' = (E \setminus \{e_1, e_2\}) \cup \{e\}\) (\(e \notin E\)),
• \(\varphi'(f) = \varphi(f)\) ha \(f \in E \setminus \{e_1, e_2\}\); \(\varphi'(e) = \{v_1, v_2\}\).

Definíció — topológiailag izomorf gráfok

Két gráf topológiailag izomorf, ha az elsőt véges sok élfelosztással és élösszevonással olyan gráffá lehet alakítani, amely izomorf a második gráffal.

Tétel — Kuratowski tétele síkbarajzolható gráfokra

Egy \(G\) gráf síkbarajzolható \(\iff G\) nem tartalmaz olyan részgráfot, amely topológiailag izomorf \(K_5\)-tel vagy \(K_{3,3}\)-mal.

Bizonyítás

⟹: elég azt belátni, hogy \(K_5\) és \(K_{3,3}\) nem síkbarajzolható.

• \(K_5\): \(|E(K_5)| = \frac{5 \cdot 4}{2} = 10\). A korábbi tétel szerint egyszerű síkgráfra \(|E| \le 3|V| - 6 = 3(5) - 6 = 9\). De \(10 \not\le 9 \implies K_5\) nem síkbarajzolható.
• \(K_{3,3}\): \(|E(K_{3,3})| = 3 \cdot 3 = 9\). Mivel \(K_{3,3}\) páros gráf, rá \(|E| \le 2|V| - 4 = 2(6) - 4 = 8\). De \(9 \not\le 8 \implies K_{3,3}\) nem síkbarajzolható.

⟸: nem bizonyítjuk.

Emlékeztető

A Kuratowski-tétel a síkbarajzolhatóság pontos (szükséges és elégséges) jellemzése. \(K_5\) a legkisebb nem síkgráf, \(K_{3,3}\) a legkisebb páros nem síkgráf (tiltott "aljzatok" / tiltott minorok).

Tétel — Fáry–Wagner-tétel

Ha \(G\) egyszerű, síkbarajzolható gráf, akkor van olyan \(G\)-vel izomorf síkbarajzolt gráf, amelyben minden él egyenes szakasz.