Twierdzenie o liczbie krawędzi pozwala stwierdzić, czy graf jest hamiltonowski.
Treść twierdzenia Jeśli graf prosty o wierzchołkach ma co najmniej
krawędzi, to jest hamiltonowski.
Dowód twierdzenia Dla dowolnego grafu prostego załóżmy, że zachodzi
i weźmy wierzchołki i takie, że:
Niech będzie grafem z którego usunięto wierzchołki i oraz kończące się w nich krawędzie. Ponieważ:
więc usunęliśmy krawędzi i dwa wierzchołki. jest podgrafem grafu a więc:
z czego wynika, że:
a więc spełnia założenia twierdzenia Orego.
Zobacz też twierdzenie Bondy’ego-Chvátala twierdzenie Diraca (1952) twierdzenie Orego
O liczbie krawędzi grafu hamiltonowskiego