Ore's theorem
From Wikipedia, the free encyclopedia
- For Ore's theorem in ring theory, see Ore condition.
Ore's theorem is a result in graph theory due to Øystein Ore (1960). It gives a sufficient condition for a graph to contain a path that starts and ends at the same vertex and includes each vertex exactly once. Such a graph is said to be Hamitonian.
It involves considering the number of edges incident to each vertex, called the degree of the vertex v, and denoted by deg(v).
[edit] Statement of the theorem
If G is a simple connected graph with n vertices, where n ≥ 3, and if for each pair of non-adjacent vertices v and w, deg(v) + deg(w) ≥ n, then G is Hamiltonian.
