A Proof of Ore's Theorem

The Strategy: From a Longest Path to a Cycle

Ore’s theorem gives a sufficient condition for a graph to have a Hamiltonian cycle: a cycle that visits every vertex exactly once before returning to its start. The proof does not try to build such a cycle directly. Instead, it begins with a longest path. Its endpoints cannot have neighbors outside the path, so their degrees count positions along that path. The degree-sum hypothesis then forces two useful edges in complementary positions, which can be joined with the path edges to make a cycle.

All graphs in this tutorial are finite and simple. A path is a sequence of distinct vertices in which consecutive vertices are adjacent; its length is its number of edges. A longest path is a path of maximum length in the graph. A Hamiltonian cycle is a cycle containing every vertex of the graph. The degree \(\deg(v)\) of a vertex \(v\) is the number of its neighbors.

The condition concerns only nonadjacent pairs. There is no requirement on the degree sum of a pair that already forms an edge. We prove the theorem by first establishing that the condition makes \(G\) connected, then using a longest path in \(G\).

The Degree-Sum Condition Forces Connectedness

Proof. Suppose instead that \(G\) is disconnected. Choose vertices \(u\) and \(v\) from two different connected components, and let those components have vertex sets \(C_u\) and \(C_v\). There is no edge between \(u\) and \(v\), so the hypothesis applies. Every neighbor of \(u\) lies in \(C_u\), and every neighbor of \(v\) lies in \(C_v\). Therefore \(\deg(u)\le |C_u|-1\) and \(\deg(v)\le |C_v|-1\). The components are disjoint and contain at most all \(n\) vertices, so \[ \deg(u)+\deg(v)\le |C_u|+|C_v|-2\le n-2<n. \] This contradicts the required degree sum. Hence \(G\) is connected. \(\square\)

Connectedness will be used at the end of the proof. If a cycle contains all the vertices of a longest path but misses other vertices of the graph, connectedness supplies an edge from the cycle to the outside. That edge would let us make a longer path.

Proof of Ore’s Theorem

Proof. Let \(G\) satisfy the hypotheses. By the lemma, \(G\) is connected. Choose a longest path and write it in order as \[ P=v_1v_2\cdots v_k. \] Since \(G\) is connected and \(n\ge3\), it has a path with at least three vertices: otherwise every path would have at most two vertices, which is impossible in a connected graph with at least three vertices. Thus \(k\ge3\).

Neither endpoint of \(P\) can have a neighbor outside \(P\), because such a neighbor could be added at that endpoint to produce a longer path. We consider whether the endpoints \(v_1\) and \(v_k\) are adjacent.

If \(v_1v_k\in E(G)\), then \(v_1v_2\cdots v_kv_1\) is a cycle containing the \(k\) vertices of \(P\). If \(k<n\), this cycle does not contain every vertex of \(G\). Since \(G\) is connected, there must be an edge \(xw\) with \(x\) outside the cycle and \(w\) on it; otherwise no vertex outside the cycle could be connected to a vertex on it. Starting at \(x\), moving to \(w\), and then following the cycle from \(w\) through its other \(k-1\) vertices gives a path with \(k+1\) distinct vertices. This contradicts the choice of \(P\) as a longest path. Hence in this case \(k=n\), and the cycle is Hamiltonian.

It remains to consider the case \(v_1v_k\notin E(G)\). Every neighbor of \(v_1\) lies among \(v_2,\ldots,v_{k-1}\); it cannot be \(v_k\), by the case assumption, or outside \(P\), by maximality of the path. Similarly, every neighbor of \(v_k\) lies among \(v_2,\ldots,v_{k-1}\). Define index sets \[ A=\{i\in\{1,\ldots,k-1\}:v_1v_{i+1}\in E(G)\},\qquad B=\{i\in\{1,\ldots,k-1\}:v_iv_k\in E(G)\}. \] The index \(k-1\) cannot belong to \(A\), because that would mean \(v_1v_k\in E(G)\). The index \(1\) cannot belong to \(B\), for the same reason. The remaining indices in \(A\) correspond one-to-one with the neighbors of \(v_1\), and the indices in \(B\) correspond one-to-one with the neighbors of \(v_k\). Thus \(|A|=\deg(v_1)\) and \(|B|=\deg(v_k)\).

The endpoints are nonadjacent, so Ore’s condition gives \(|A|+|B|=\deg(v_1)+\deg(v_k)\ge n\). Also \(k\le n\), so \(|A|+|B|\ge k\). Both sets lie in a universe of \(k-1\) indices. If they were disjoint, their total size would be at most \(k-1\), a contradiction. Choose \(j\in A\cap B\). Since \(1\notin B\) and \(k-1\notin A\), we have \(2\le j\le k-2\). By the definitions of \(A\) and \(B\), both \(v_1v_{j+1}\) and \(v_jv_k\) are edges.

Now use the path edges from \(v_1\) to \(v_j\), the edge \(v_jv_k\), the path edges backwards from \(v_k\) to \(v_{j+1}\), and finally the edge \(v_{j+1}v_1\). They form the cycle \[ v_1,v_2,\ldots,v_j,v_k,v_{k-1},\ldots,v_{j+1},v_1. \] Every vertex \(v_1,\ldots,v_k\) occurs exactly once before the return to \(v_1\). This is a cycle containing all vertices of \(P\). If \(k<n\), connectedness again gives an edge from a vertex outside this cycle to a vertex on it. Starting with the outside vertex and then following the cycle through all \(k\) vertices gives a path with \(k+1\) distinct vertices, contradicting that \(P\) was longest. Therefore \(k=n\), and the cycle is Hamiltonian. This proves Ore’s theorem. \(\square\)

Worked Examples: Tracing the Index-Set Argument

Common Pitfall: Testing Adjacent Pairs

A tempting but incorrect check is to test the degree sum of every pair, including adjacent pairs. For example, in the four-cycle above, vertices \(1\) and \(2\) are adjacent and have degree sum \(2+2=4\). That happens to meet the threshold, but this calculation is not part of the hypothesis. In other graphs an adjacent pair may have a smaller degree sum without affecting Ore’s condition. The correct test is to identify the nonadjacent pairs and check only those.

There is a second important distinction: the conclusion is sufficient, not a claim that every Hamiltonian graph must satisfy the degree-sum condition. If the condition fails, this proof gives no conclusion. For instance, let \(G\) be the star with vertex set \(\{c,1,2,3\}\) and edge set \(\{c1,c2,c3\}\). Its leaves have degree \(1\), so a nonadjacent pair of leaves has degree sum \(1+1=2<4\). This graph has no Hamiltonian cycle: each leaf has only one incident edge, whereas a cycle through that leaf would require two distinct incident edges. The failed condition explains why Ore’s theorem cannot be applied; it is not an exception to the theorem.