Using Ore’s Criterion
A graph can have many edges, but Ore’s degree-sum criterion does not ask us to test every edge. It asks us to inspect the pairs that are not edges. For each such pair, we add the degrees of its endpoints and compare the sum with the number of vertices. If every nonedge passes this test, Ore’s theorem certifies that the graph has a Hamiltonian cycle.
All graphs in this tutorial are finite and simple: there are no loops or multiple edges. A Hamiltonian cycle is a cycle that visits every vertex exactly once before returning to its starting vertex. A pair of distinct vertices \(u,v\) is a nonedge when \(uv\notin E(G)\). The degree \(\deg(v)\) is the number of vertices adjacent to \(v\).
The test has two distinct outcomes. If every nonedge satisfies the inequality, the theorem gives a Hamiltonian cycle. If even one nonedge fails, the theorem gives no conclusion: the graph might still be Hamiltonian, or it might not be. The condition is sufficient, not a test that characterizes all Hamiltonian graphs.
How to Check the Condition
First compute all vertex degrees. Then consider each nonedge exactly once, add its endpoint degrees, and compare the result with \(n\). There is no need to test adjacent pairs: Ore’s hypothesis concerns nonadjacent vertices only.
Find \(n=|V(G)|\), then compute \(\deg(v)\) for every vertex \(v\).
For each unordered pair of distinct vertices, include it only if it is absent from \(E(G)\).
For each listed pair \(uv\), calculate \(\deg(u)+\deg(v)\). A sum below \(n\) means Ore’s condition fails; if no pair fails, the theorem certifies Hamiltonicity.
This procedure can be organized around the nonedge list. Once the degrees are known, checking a supplied list of \(\overline m\) nonedges takes \(\overline m\) degree-sum comparisons. If the graph is given by an ordinary edge list instead, one must also determine which vertex pairs are absent; that bookkeeping is separate from the degree-sum test. In either format, the mathematical condition is precisely a check over all nonedges.
Proof. Suppose first that every nonedge \(uv\) has \(\deg(u)+\deg(v)\ge n\). If there is at least one nonedge, its degree sums form a finite set, and each member is at least \(n\); therefore the smallest member is at least \(n\). Conversely, if the smallest degree sum among nonedges is at least \(n\), every degree sum in that set is at least its smallest member and hence at least \(n\). If there are no nonedges, there is no pair that can violate Ore’s condition, so its universal requirement is satisfied. \(\square\)
Worked Applications
Worked Example: A Complete Bipartite Graph
Let \(G=(V,E)\) have \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,14,16,32,34,36,52,54,56\}\). Decide whether Ore’s condition applies.
The order is \(n=6\). From the edge list, vertices \(1,3,5\) are each adjacent to \(2,4,6\), and vertices \(2,4,6\) are each adjacent to \(1,3,5\). Thus every vertex has degree \(3\). The absent pairs are the pairs within \(\{1,3,5\}\) and within \(\{2,4,6\}\): \(13,15,35,24,26,46\). There are no other nonedges because all nine pairs between the two groups appear in the edge list.
For each listed nonedge, both endpoints have degree \(3\), so each degree sum is \(3+3=6\). Since \(n=6\), every sum meets the required inequality \(6\ge6\). By Ore’s theorem, \(G\) is Hamiltonian.
Check: The sequence \(1,2,3,4,5,6,1\) is a Hamiltonian cycle: its successive edges are \(12,23,34,45,56,61\), and all are in \(E\). It visits all six vertices once before returning to \(1\). As an independent degree check, the degree sum is \(6\cdot3=18\), while the edge list has \(9\) edges and hence \(2|E|=2\cdot9=18\).
Worked Example: A Graph Missing Three Disjoint Edges
Let \(V=\{1,2,3,4,5,6,7\}\), and define \(E=\binom{V}{2}\setminus\{12,34,56\}\), where \(\binom{V}{2}\) is the set of all unordered pairs of distinct vertices. Thus the graph is complete except for the three specified nonedges. Test Ore’s condition.
Each of vertices \(1,\dots,6\) is adjacent to the other five vertices except for its partner in one of the missing pairs. Therefore \(\deg(1)=\deg(2)=\deg(3)=\deg(4)=\deg(5)=\deg(6)=5\). Vertex \(7\) is adjacent to all six other vertices, so \(\deg(7)=6\). The order is \(n=7\), and the only nonedges are \(12,34,56\).
The degree sum at each nonedge is \(5+5=10\). Since \(10\ge7\), all three nonedges pass, and there are no others to check. Ore’s theorem therefore certifies that \(G\) is Hamiltonian.
Check: One Hamiltonian cycle is \(1,3,5,2,4,6,7,1\). Its successive pairs are \(13,35,52,24,46,67,71\); none is one of the missing pairs \(12,34,56\), so every successive pair is an edge. The cycle includes all seven vertices once. Also, the degree sum is \(6\cdot5+6=36\). The graph has \(\binom{7}{2}-3=21-3=18\) edges, so \(2|E|=2\cdot18=36\), in agreement with the degree sum.
Worked Example: A Failed Test Does Not Rule Out Hamiltonicity
Let \(G=(V,E)\) have \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,23,34,45,56,61\}\). Determine whether Ore’s theorem certifies Hamiltonicity, and interpret the result.
Every vertex has degree \(2\), because each is incident with exactly the two cycle edges next to it. The order is \(n=6\). The nonedges are \(13,14,15,24,25,26,35,36,46\). These are all the remaining pairs: there are \(\binom{6}{2}=15\) unordered pairs in total, and \(15-6=9\) are absent, matching the nine listed nonedges.
For every nonedge \(uv\), the sum is \(\deg(u)+\deg(v)=2+2=4\). Since \(4<6=n\), every one of these pairs violates Ore’s required inequality. Thus Ore’s condition fails, and the theorem does not certify this graph.
Check: Despite the failed test, the edge list itself is the cycle \(1,2,3,4,5,6,1\). It visits all six vertices exactly once before returning to its start, so \(G\) is Hamiltonian. This example confirms that failure of Ore’s condition does not imply non-Hamiltonicity.
What a Successful or Failed Test Tells You
A successful check is a certificate by a sufficient condition: once the hypotheses and every nonedge inequality have been verified, Ore’s theorem guarantees a Hamiltonian cycle. In an application, keep the verification visible. Record \(n\), the vertex degrees, the complete list of nonedges, and the sum for each one. This makes it possible to see that no pair was omitted or mistakenly treated as an edge.
A failed check has a narrower meaning. It identifies a nonedge \(uv\) with \(\deg(u)+\deg(v)<n\), so the hypothesis of Ore’s theorem is not satisfied. The conclusion is only that this theorem cannot certify Hamiltonicity for this graph. The 6-cycle example shows why it would be an error to conclude that the graph has no Hamiltonian cycle.
When the graph has no nonedges, every distinct pair is adjacent. The condition is then true because there is no nonedge to test. For \(n\ge3\), Ore’s theorem applies. In all cases, keep the order hypothesis \(n\ge3\) in view: it is part of the theorem, not a quantity to replace with the number of edges or the number of nonedges.
Common Pitfalls
Testing edges instead of nonedges. In the first example, checking only \(12\) would compute \(3+3=6\), but that does not test Ore’s condition: \(12\) is an edge. The correct check lists \(13,15,35,24,26,46\), the absent pairs, and verifies the sum for each.
Using the wrong threshold. The comparison is with the order \(n=|V(G)|\), not the size \(m=|E(G)|\), the maximum degree, or the number of nonedges. For the second example, the threshold is \(7\), even though the graph has \(18\) edges.
Turning a failed hypothesis into a negative conclusion. The incorrect inference “some nonedge has degree sum below \(n\), so the graph is not Hamiltonian” does not follow from Ore’s theorem. In the third example, the calculation \(2+2=4<6\) shows that the criterion fails, while the listed cycle directly verifies Hamiltonicity.
Check Your Understanding
For each question, distinguish what Ore’s condition verifies from what it does not establish.
- For a graph of order \(8\), a nonedge has endpoint degrees \(3\) and \(5\). Does this pair satisfy Ore’s inequality?
- Let \(V=\{1,2,3,4,5\}\) and \(E=\{12,13,14,15,23,24,25,34,35\}\). Compute every degree and check Ore’s condition.
- Why is it enough to test nonedges, rather than all pairs of vertices?
- A graph has one nonedge \(uv\) with \(\deg(u)+\deg(v)<n\). What conclusion about Hamiltonicity is justified by this observation alone?
- Explain why a graph with no nonedges satisfies Ore’s condition, and state the order hypothesis required to invoke the theorem.