Wzór Eulera (teoria grafów)

Wzór Eulera, wzór Eulera dla grafów płaskich – twierdzenie teorii grafów opisujące zależność między liczbą wierzchołków, ścian i krawędzi grafu płaskiego.

Teza

Niech $G$ będzie spójnym grafem płaskim i niech liczba wierzchołków, krawędzi i ścian grafu $G$ wynosi odpowiednio: $\nu =\nu (G)=|V|,$ $\varepsilon =\varepsilon (G)=|E|$ i $\varphi =\varphi (G)=|S|.$ Wówczas:

$\nu -\varepsilon +\varphi =2.$

Dowód

Dowód metodą indukcji matematycznej względem liczby krawędzi $\varepsilon$ spójnego płaskiego grafu $G.$ Jeśli $\varepsilon =0,$ to ponieważ graf jest spójny $\nu =\nu (G)=1$ oraz $\varphi =\varphi (G)=1$ (ściana nieograniczona). Twierdzenie jest więc prawdziwe w tym przypadku. Założymy teraz, że twierdzenie zachodzi dla dowolnego spójnego grafu płaskiego o $\varepsilon -1$ krawędziach i pokażemy, że zachodzi wtedy również dla spójnego grafu płaskiego $G$ o $\varepsilon$ krawędziach. Zauważmy, że jeżeli $G$ jest drzewem na $\nu$ wierzchołkach, to $\varepsilon =\nu -1$ i $\varphi =\varphi (G)=1,$ a więc

$\nu -\varepsilon +\varphi =\nu -(\nu -1)+1=\nu -\nu +1+1=2.$

Stąd twierdzenie jest prawdziwe dla dowolnego drzewa.Załóżmy więc, że $G$ nie jest drzewem. Istnieje wtedy co najmniej jeden cykl. Niech $e$ będzie krawędzią zawartą w pewnym cyklu grafu $G.$ Wówczas $e$ należy do brzegu dokładnie dwóch ścian i $e$ nie jest krawędzią cięcia. Wyrzucenie krawędzi $e$ spowoduje więc powstanie z tych dwóch ścian jednej ściany i nie rozspójni grafu $G.$ $G-e$ jest więc spójnym grafem płaskim z $\nu$ wierzchołkami, $\varepsilon -1$ krawędziami i $\varphi -1$ ścianami. Możemy więc dla grafu $G-e$ zastosować założenie indukcyjne:

$\nu (G-e)-\varepsilon (G-e)+\varphi (G-e)=\nu -(\varepsilon -1)+(\varphi -1)=2,$

co po przekształceniach daje: $\nu -\varepsilon +\varphi =2.$ Na mocy zasady indukcji matematycznej twierdzenie zachodzi dla dowolnego spójnego grafu płaskiego $G.$

Wnioski

• Wszystkie grafy płaskie danego spójnego grafu planarnego mają taką samą liczbę ścian.
• Jeżeli $G$ jest planarnym grafem i $\nu \geqslant 2$ oraz jego talia (długość najkrótszego cyklu) wynosi $r,$ to: $(r-2)\varepsilon \leqslant r(\nu -2).$
• Jeżeli $G$ jest planarnym grafem prostym i $\nu \geqslant 3,$ to: $\varepsilon \leqslant 3\nu -6.$
• Jeżeli $G$ jest planarnym grafem prostym i $\nu \geqslant 3$ oraz $G$ nie ma trójkątów (cykli długości 3), to: $\varepsilon \leqslant 2\nu -4.$
• Graf Kuratowskiego $K_{5}$ nie jest planarny.
• Graf Kuratowskiego $K_{3,3}$ nie jest planarny.
• Graf Petersena nie jest planarny.
• Jeżeli $G$ jest planarnym grafem prostym, to $G$ zawiera wierzchołek stopnia co najwyżej 5, to znaczy $\delta (G)\leqslant 5.$
• Jeżeli $G$ jest grafem płaskim o $\omega$ składowych spójności, to: $\nu -\varepsilon +\varphi =\omega +1.$

Uogólnienie

Jeżeli G jest grafem spójnym, którego genus wynosi $g,$ to:

$|V|+|S|-|E|=2-2g.$

Zobacz też

• charakterystyka Eulera
• graf planarny
• twierdzenie Eulera o wielościanach

Bibliografia

• Robin J. Wilson: Wprowadzenie do teorii grafów. Warszawa: PWN, 1998.brak strony w książce
• Victor Bryant: Aspekty kombinatoryki. Warszawa: WNT, 1997.brak strony w książce
• J.H. van Lint, R.M. Wilson: A course in combinatorics. Cambridge: Cambridge University Press, 1992.brak strony w książce

Linki zewnętrzne

• Dwadzieścia dowodów twierdzenia Eulera (ang.)