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 Hamiltonian.

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.

[edit] See also

• Bondy-Chvátal theorem