PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: High Entry average rating: No information on entry rating
Ore's theorem (Theorem)

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




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

View style:

See Also: Hamiltonian graph, Bondy and Chvátal theorem

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 4146 times total.

Classification:
AMS MSC05C45 (Combinatorics :: Graph theory :: Eulerian and Hamiltonian graphs)

Pending Errata and Addenda
None.
[ View all 2 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | prove | add result | add corollary | add example | add (any)