Príklady grafov
Rovinné	Nerovinné
	K5
Kompletný graf K4	K3,3

Rovinný graf alebo planárny graf je taký graf G = (V, H), ktorého diagram v rovine možno zostrojiť tak, že dve rôzne hrany majú spoločné nanajvýš krajné vrcholy. Inými slovami: graf je rovinný, ak sa dá nakresliť v rovine tak, že vrcholy sú body roviny, hrany sú oblúky (krivky) a žiadne dve hrany sa nepretínajú.

Medzi rovinné grafy patria všetky stromy a grafy ${\displaystyle K_{1},K_{2},K_{3},K_{4}}$, teda všetky grafy s počtom vrcholov minimálne jedna a maximálne štyri. Ďalšou charakteristikou je fakt, že Eulerova veta je platná pre akýkoľvek planárny graf.

Eulerova veta

Eulerova veta: v + s = h + 2; kde v – počet vrcholov, s – počet oblastí (štátov), h – počet hrán (hraníc).

Dôkaz

Dôkaz Eulerovej vety urobíme indukciou vzhľadom na počet hrán ${\displaystyle h}$. Veta zrejme platí v grafoch bez hrán. Predpokladajme teraz, že platí pre všetky rovinné grafy, ktoré majú menej ako ${\displaystyle h}$ hrán (indukčný predpoklad). Nech ${\displaystyle G}$ je rovinný graf s ${\displaystyle h}$ hranami. Budeme rozlišovať dva prípady:

a) Nech ${\displaystyle G}$ obsahuje most. Potom po vynechaní mostu sa rozpadne na dva rovinné grafy ${\displaystyle G_{1}}$, ${\displaystyle G_{2}}$. Nech počet vrcholov, hrán a oblastí grafu ${\displaystyle G_{1}}$ je ${\displaystyle v_{1}}$, ${\displaystyle h_{1}}$, ${\displaystyle s_{1}}$ a grafu ${\displaystyle G_{2}}$ je ${\displaystyle v_{2}}$, ${\displaystyle h_{2}}$, ${\displaystyle s_{2}}$. Pre ${\displaystyle G_{1}}$ a ${\displaystyle G_{2}}$ už (podľa indukčného predpokladu) veta platí. Teda máme ${\displaystyle h_{1}=v_{1}+s_{1}-2}$, ${\displaystyle h_{2}=v_{2}+s_{2}-2}$. Ďalej ${\displaystyle v_{1}+v_{2}=v}$ – počet vrcholov grafu ${\displaystyle G}$, ${\displaystyle h_{1}+h_{2}=h-1}$, ${\displaystyle s_{1}+s_{2}=s+1}$ (vynechaním mostu sa počet oblastí nemení, ale v súčte ${\displaystyle s_{1}+s_{2}}$ sa vonkajšia oblasť započíta dvakrát). Z posledných rovností a z uvedených vzťahov vyššie dostaneme: ${\displaystyle h=h_{1}+h_{2}+1=(v_{1}+s_{1}-2)+(v_{2}+s_{2}-2)+1=(v_{1}+v_{2})+(s_{1}+s_{2})-3=v+(s+1)-3=v+s-2}$.

b) Nech ${\displaystyle G}$ neobsahuje most. Potom zoberme ľubovolnú hranu ${\displaystyle h}$. Hrana ${\displaystyle h}$ je obsiahnutá v nejakej kružnici. Zoberme najkratšiu kružnicu ${\displaystyle C}$, v ktorej je hrana ${\displaystyle h}$ obsiahnutá. Vnútri kružnice ${\displaystyle C}$ sa pri vhodnom kreslení diagramu grafu nachádza nejaká oblasť, ktorá vynechaním hrany ${\displaystyle h}$ zanikne. Teda, ak ${\displaystyle G'}$ má práve o jednu oblasť menej ako ${\displaystyle G}$. Pritom má ten istý počet vrcholov. Pre ${\displaystyle G'}$ však veta platí, preto platí aj pre ${\displaystyle G}$. Tým je dôkaz ukončený.

Dôsledky Eulerovej vety

Dôsledok 1

Ak ${\displaystyle G}$ je rovinný graf, v ktorom všetky oblasti sú ohraničené kružnicami ${\displaystyle C_{n}}$, tak ${\displaystyle h={\frac {n(v-2)}{n-2}}}$.

Dôsledok 2

Keď ${\displaystyle G}$ je rovinný graf s ${\displaystyle v\geq 3}$ vrcholmi a s maximálnym počtom hrán, tak každá oblasť je ${\displaystyle C_{3}}$ a platí ${\displaystyle h=3v-<!--\; -\; -->}$Zdroj:
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.