PlanetMath: Ore's theorem

(more info)

Math for the people, by the people.

Main Menu

Ore's theorem

(Theorem)

Let be a simple graph of order $n\ge 3$ such that, for every pair of distinct non adjacent vertices and , $\deg(u)+\deg(v)\ge n$ . Then is a Hamiltonian graph.

"Ore's theorem" is owned by Koro. [ full author list (2) | owner history (1) ]

(view preamble)

Log in to rate this entry.
(view current ratings)

Cross-references: Hamiltonian graph, adjacent vertices, order, simple graph
There is 1 reference to this entry.

This is version 5 of Ore's theorem, born on 2001-10-24, modified 2006-09-20.
Object id is 473, canonical name is OresTheorem.
Accessed 3394 times total.

Classification:

05C45 (Combinatorics :: Graph theory :: Eulerian and Hamiltonian graphs)

Pending Errata and Addenda

None.[ View all 2 ]

Discussion

forum policy

No messages.

Interact