Twierdzenie o ilości krawędzi (graf hamiltonowski)
Z Wikipedii
Spis treści |
[edytuj] Twierdzenie o ilości krawędzi
Twierdzenie o ilości krawędzi pozwala stwierdzyć, czy graf jest hamiltonowski.
[edytuj] Treść twierdzenia
Jeśli graf prosty o n wierzchołkach ma co najmniej m krawędzi, gdzie:
to jest hamiltonowski.
[edytuj] Dowód twierdzenia
Dla dowolnego grafu prostego G załózmy, że zachodzi
i weżmy wierzchołki v i u takie, że:
.
Niech H będzie grafem G z którego usunięto wierzchołki v i u oraz kończące się w nich krawędzie. Ponieważ:
więc usunęliśmy deg(v) + deg(u) krawędzi i dwa wierzchołki. H jest podgrafem grafu Kn − 2, a więc:
z czego wynika, że:
a więc G spełnia założenia twierdzenia Ore.
