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 będzie spójnym grafem płaskim i niech liczba wierzchołków, krawędzi i ścian grafu wynosi odpowiednio: i Wówczas:
Dowód Dowód metodą indukcji matematycznej względem liczby krawędzi spójnego płaskiego grafu Jeśli to ponieważ graf jest spójny oraz (ś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 krawędziach i pokażemy, że zachodzi wtedy również dla spójnego grafu płaskiego o krawędziach. Zauważmy, że jeżeli jest drzewem na wierzchołkach, to i a więc
Stąd twierdzenie jest prawdziwe dla dowolnego drzewa.Załóżmy więc, że nie jest drzewem. Istnieje wtedy co najmniej jeden cykl. Niech będzie krawędzią zawartą w pewnym cyklu grafu Wówczas należy do brzegu dokładnie dwóch ścian i nie jest krawędzią cięcia. Wyrzucenie krawędzi spowoduje więc powstanie z tych dwóch ścian jednej ściany i nie rozspójni grafu jest więc spójnym grafem płaskim z wierzchołkami, krawędziami i ścianami. Możemy więc dla grafu zastosować założenie indukcyjne:
co po przekształceniach daje: Na mocy zasady indukcji matematycznej twierdzenie zachodzi dla dowolnego spójnego grafu płaskiego
Wnioski Wszystkie grafy płaskie danego spójnego grafu planarnego mają taką samą liczbę ścian. Jeżeli jest planarnym grafem i oraz jego talia (długość najkrótszego cyklu) wynosi to: Jeżeli jest planarnym grafem prostym i to: Jeżeli jest planarnym grafem prostym i oraz nie ma trójkątów (cykli długości 3), to: Graf Kuratowskiego nie jest planarny. Graf Kuratowskiego nie jest planarny. Graf Petersena nie jest planarny. Jeżeli jest planarnym grafem prostym, to zawiera wierzchołek stopnia co najwyżej 5, to znaczy Jeżeli jest grafem płaskim o składowych spójności, to:
Uogólnienie Jeżeli G jest grafem spójnym, którego genus wynosi to:
Zobacz też charakterystyka Eulera graf planarny twierdzenie Eulera o wielościanach
Bibliografia
Linki zewnętrzne Dwadzieścia dowodów twierdzenia Eulera
Kategoria:Teoria grafów