Definice. Roviný graf je graf, který má rovinné nakreslení.
Definice. Dělení grafu $G$ je graf $G'$, který vyrobíme z grafu $G$ tak, že některé jeho hrany nahradíme cestami.
Kuratovského věta. Graf je rovinný, právě když neobsahuje jako svůj podgraf dělení $K_{3,3}$ ani $K_5$.
Věta (Eulerova formule). Mějme souvislý rovinný graf $G(V,E)$ a jeho nakreslení, které má $F$ stěn ($F$ podle anglického "faces"). Pak $|V|-|E|+|F|=2$.
Věta. $G(V,E)$ budiž rovinný graf na alespoň 3 vrcholech. Pak $|E|\leq 3|V|-6$. Pokud v $G$ navíc neexistuje trojúhelník, pak dokonce $|E|<2|V|-4$.
Důsledek. V každém rovinném grafu existuje vrchol, jehož stupeň je nejvýše 5.
Definice. Duální graf (multi)grafu $G$ je multigraf takový, že jeho vrcholy jsou stěny původního grafu, a jeho hrany jsou právě tam, kde měly původní stěny společnou hranu.
Poznámka. I duální graf normálního grafu může být multigraf. Duální graf grafu nemusí být určen jednoznačně, může záležet na nakreslení. Pokud však mezi opakováním operace "Najdi duál" nebudeme nakreslení měnit, platí, že duál duálu souvislého rovinného grafu $G$ je opět $G$.
Příklad 1. Najděte graf, jehož dvě různá nakreslení vedou na dva různé neizomorfní duály.
Příklad 2. Může existovat 3-regulární graf, jehož všechny stěny budou šestiúhelníky? A pětiúhelníky?
Příklad 3. Dokažte, že pro každý graf $G$ na jedenácti vrcholech buď $G$ nebo $\overline G$ není rovinný.
Příklad 4. Nakreslete $K_{3,3}$ na torus.
Příklad 5. Nakreslete $Q_4$ na torus.
Příklad 6. (hvězdičkový) Mějme zadané číslo $n$. Zkonstruujte graf, jehož barevnost bude alespoň $n$, ale přitom ale který nebude obsahovat $K_3$ jako podgraf.
Najděte postup, jak z grafu bez trojúhelníku $G(V,E)$ s barevností $n$ udělat graf bez trojúhelníku o $2|V|+1$ vrcholech, který bude mít barevnost $n+1$.
Příklad 7. Dokažte že duál eulerovského grafu je 2-obarvitelný. Musí být naopak duál 2-obarvitelného rovinného grafu eulerovský?
Příklad 8. Hranový graf grafu $G(V,E)$, který má alespoň jednu hranu, je graf $L(G)(E,E')$ tak, že $\{e_1e_2\} \in E' \Leftrightarrow e_1\cap e_2\neq \emptyset$, tedy vrcholy jsou původní hrany a hrany spojují vrcholy reprezentující hrany, co měly společný vrchol. Určete barevnost $L(K_n)$.
Příklad 9. (hvězdičkový) Mějme nekonečný graf, jehož vrcholy jsou všechny body roviny, a hrana vede právě mezi těmi dvojicemi bodů, jejichž (eukleidovská) vzdálenost je 1. Barevnost tohoto grafu je otevřený problém, ví se, že je to buď 5, 6 nebo 7 (a je možné, že záleží na výběru axiomů teorie množin; o tom však jindy). Zkuste sami najít obarvení tohoto grafu 7 barvami a dokázat, že nemůže existovat obarvení 3 barvami.