Ore's theorem is a result in graph theory proved in 1960 by Norwegian mathematician Øystein Ore. It gives a sufficient condition for a graph to be Hamiltonian, essentially stating that a graph with sufficiently many edges must contain a Hamilton cycle. Specifically, the theorem considers the sum of the degrees of pairs of non-adjacent vertices: if every such pair has a sum that at least equals the total number of vertices in the graph, then the graph is Hamiltonian. Formal statement Let be a (finite and simple) graph with vertices. We denote by the degree of a vertex in , i.e. the number of incident edges in to . Then, Ore's theorem states that if then is Hamiltonian. Proof It is equivalent to show that every non-Hamiltonian graph does not obey condition (∗). Accordingly, let be a graph on vertices that is not Hamiltonian, and let be formed from by adding edges one at a time that do not create a Hamiltonian cycle, until no more edges can be added. Let and be any two non-adjacent vertices in . Then adding edge to would create at least one new Hamiltonian cycle, and the edges other than in such a cycle must form a Hamiltonian path in with and . For each index in the range , consider the two possible edges in from to and from to . At most one of these two edges can be present in , for otherwise the cycle would be a Hamiltonian cycle. Thus, the total number of edges incident to either or is at most equal to the number of choices of , which is . Therefore, does not obey property (∗), which requires that this total number of edges () be greater than or equal to . Since the vertex degrees in are at most equal to the degrees in , it follows that also does not obey property (∗). Algorithm describes the following simple algorithm for constructing a Hamiltonian cycle in a graph meeting Ore's condition. Arrange the vertices arbitrarily into a cycle, ignoring adjacencies in the graph. While the cycle contains two consecutive vertices vi and vi + 1 that are not adjacent in the graph, perform the following two steps: Search for an index j such that the four vertices vi, vi + 1, vj, and vj + 1 are all distinct and such that the graph contains edges