What Sharpness Means for Ore’s Bound
A sufficient condition guarantees a Hamiltonian cycle when its hypotheses hold; it need not describe every graph that has such a cycle. To ask whether a numerical threshold is sharp is to ask whether it can be weakened. Here the question is whether Ore’s degree-sum threshold can be reduced by one while still guaranteeing a Hamiltonian cycle.
All graphs in this tutorial are finite and simple. A Hamiltonian cycle is a cycle that contains every vertex of the graph. A graph is Hamiltonian if it contains such a cycle. For a graph \(G=(V,E)\) of order \(n=|V|\), Ore’s theorem states that if \(n\ge3\) and every pair of distinct nonadjacent vertices \(u,v\) satisfies \(\deg(u)+\deg(v)\ge n\), then \(G\) is Hamiltonian. This result was proved in the earlier material on Ore’s theorem.
To test whether the bound \(n\) can be lowered to \(n-1\), we need a graph that is not Hamiltonian but for which every nonadjacent pair has degree sum at least \(n-1\). The construction below does more: every nonadjacent pair has degree sum exactly \(n-1\).
Two Complete Graphs Sharing One Vertex
The shared vertex is counted only once in \(V(G)=A\cup B\). Therefore the order is \(n=r+s-1\). Each vertex in \(A\setminus\{x\}\) is adjacent to the other \(r-1\) vertices of \(A\), and to no vertex in \(B\setminus\{x\}\), so its degree is \(r-1\). Likewise, every vertex in \(B\setminus\{x\}\) has degree \(s-1\). The shared vertex is adjacent to every other vertex, so its degree is \(r+s-2\).
Within either set, every pair of distinct vertices is adjacent. A nonadjacent pair must therefore consist of one vertex \(a\in A\setminus\{x\}\) and one vertex \(b\in B\setminus\{x\}\). For such a pair, the degree sum is \(r-1+s-1=r+s-2=n-1\). This calculation gives the exact one-unit gap from Ore’s condition.
Proof. The order and degrees follow from the construction and calculations above. Since \(r,s\ge2\), both \(A\setminus\{x\}\) and \(B\setminus\{x\}\) are nonempty. Every vertex in the first set is nonadjacent to every vertex in the second, and these are the only nonadjacent pairs. Their degree sums are \((r-1)+(s-1)=r+s-2=n-1\).
It remains to show that the graph is not Hamiltonian. Suppose it had a Hamiltonian cycle. Removing \(x\) and its two incident cycle edges from that cycle would leave a path containing every vertex other than \(x\); in particular, that path would be connected. But in the graph with \(x\) removed, there are no edges between \(A\setminus\{x\}\) and \(B\setminus\{x\}\). Both sets are nonempty, so a path using all the remaining vertices cannot connect them. This contradiction proves that the graph has no Hamiltonian cycle. \(\square\)
Worked Examples
Worked Example: Two Copies of \(K_4\)
Let \(A=\{x,a_1,a_2,a_3\}\) and \(B=\{x,b_1,b_2,b_3\}\). The graph has vertex set \(V=A\cup B\) and edge set consisting of all pairs within \(A\) and all pairs within \(B\), with no edges between \(A\setminus\{x\}\) and \(B\setminus\{x\}\). Thus \(n=4+4-1=7\).
The shared vertex \(x\) has degree \(6\), since it is adjacent to \(a_1,a_2,a_3,b_1,b_2,b_3\). Each of the other six vertices has degree \(3\), because it is adjacent to the other three vertices in its own \(K_4\). The only nonadjacent pairs are \(a_i,b_j\), where \(1\le i,j\le3\). For each of these pairs, the degree sum is \(3+3=6=7-1=n-1\).
Check: Each \(K_4\) has \(\binom{4}{2}=6\) edges, and the two edge sets are disjoint, so the graph has \(6+6=12\) edges. The degree sum is \(6+6\cdot3=24\), and \(24/2=12\), agreeing with the direct edge count. The graph is not Hamiltonian: after removing \(x\), the two sets \(\{a_1,a_2,a_3\}\) and \(\{b_1,b_2,b_3\}\) have no edges between them.
Worked Example: \(K_3\) and \(K_6\) Sharing a Vertex
Let \(A=\{x,a_1,a_2\}\) and \(B=\{x,b_1,b_2,b_3,b_4,b_5\}\), and include every edge within \(A\) and within \(B\), with no other edges. The order is \(n=3+6-1=8\). The degrees are \(\deg(x)=7\), \(\deg(a_1)=\deg(a_2)=2\), and \(\deg(b_i)=5\) for \(1\le i\le5\).
Every nonadjacent pair is \(a_j,b_i\). Its degree sum is \(2+5=7=8-1\). Vertices within \(A\) or within \(B\) are adjacent, so there are no other nonadjacent pairs to check.
Check: The two complete subgraphs contribute \(\binom{3}{2}=3\) and \(\binom{6}{2}=15\) edges, for a total of \(18\). The degree sum is \(7+2\cdot2+5\cdot5=7+4+25=36\); dividing by \(2\) gives \(18\). Removing \(x\) leaves the nonempty sets \(\{a_1,a_2\}\) and \(\{b_1,b_2,b_3,b_4,b_5\}\) with no edges between them, so the graph cannot have a Hamiltonian cycle.
Worked Example: The Smallest Member of the Family
Take \(A=\{x,a\}\) and \(B=\{x,b\}\). The vertex set is \(V=\{x,a,b\}\), and the edge set is \(E=\{xa,xb\}\). This is the path with three vertices, and \(n=2+2-1=3\).
The degrees are \(\deg(x)=2\) and \(\deg(a)=\deg(b)=1\). The only nonadjacent pair is \(a,b\), and its degree sum is \(1+1=2=3-1\). There is no cycle containing all three vertices: the graph has no edge \(ab\), and its edge set consists only of \(xa\) and \(xb\).
Check: The degree sum is \(2+1+1=4\), so the number of edges is \(4/2=2\), matching the two edges listed. This example also confirms the boundary case \(n=3\) in the construction.
Why the Bound Cannot Be Lowered
Proof. Fix any \(n\ge3\), and choose \(r=2\) and \(s=n-1\). These values satisfy \(r,s\ge2\) and \(r+s-1=n\). The theorem gives a graph of order \(n\) that is not Hamiltonian, while every nonadjacent pair has degree sum exactly \(n-1\). Hence the condition that every nonadjacent pair have degree sum at least \(n-1\) does not guarantee a Hamiltonian cycle. Since these examples meet the lowered threshold exactly, the threshold \(n\) in Ore’s theorem cannot be decreased by one. \(\square\)
This is a sharpness example for a sufficient condition, not a claim that Ore’s condition is necessary for Hamiltonicity. It establishes precisely that the proposed weaker numerical condition fails: for every allowed order, there is a non-Hamiltonian graph satisfying it. In particular, checking only that degree sums are “close to” \(n\) is not enough; the distinction between \(n-1\) and \(n\) matters for this theorem.
Common Pitfall
A frequent counting error is to add the orders of the two complete graphs without correcting for their shared vertex. If the sizes are \(r\) and \(s\), the incorrect calculation \(n=r+s\) would lead to the claim that a cross-pair degree sum \(r+s-2\) is \(n-2\). The correction is that \(x\) belongs to both sets but is one vertex in the union, so \(n=r+s-1\). Consequently, \(r+s-2=n-1\), exactly one below Ore’s threshold.
A second mistake is to infer that the graph must have a Hamiltonian cycle because each complete subgraph has many edges. A Hamiltonian cycle must visit vertices on both sides and return to its starting point without repeating a vertex. Here the two sides meet only at \(x\); removing \(x\) separates the remaining vertices into two nonempty sets with no joining edge. The explicit contradiction in the theorem proof is what rules out a Hamiltonian cycle.
Check Your Understanding
Use the construction and the degree calculations above to answer these questions.
- For \(r=5\) and \(s=4\), find the order of the graph and the degree sum of a nonadjacent pair.
- In the construction, why are there no nonadjacent pairs involving the shared vertex \(x\)?
- For \(n=9\), choose \(r=2\) and \(s=n-1\). Find the degrees of the vertices in \(A\setminus\{x\}\) and \(B\setminus\{x\}\), and verify the degree sum for a nonadjacent pair.
- Explain why deleting \(x\) from a proposed Hamiltonian cycle leaves a connected path containing all other vertices.
- What does the construction prove about replacing Ore’s threshold \(n\) by \(n-1\), and what does it not prove about the necessity of Ore’s condition?