Ore's Theorem: Statement and Examples

From Minimum Degree to Degree Sums

Dirac’s criterion tests every vertex against the same threshold: the minimum degree must be at least half the order. Ore’s theorem uses a different test. It examines pairs of vertices that are not adjacent and asks whether the sum of their degrees is large enough. This distinction matters: a graph may have vertices below Dirac’s minimum-degree threshold and still meet Ore’s condition.

All graphs in this tutorial are finite and simple. A Hamiltonian cycle is a cycle that contains every vertex of the graph. In particular, a graph has a Hamiltonian cycle only if it has at least three vertices. The degree $\deg(v)$ of a vertex $v$ is the number of its neighbors.

Theorem (Ore): Let $G$ be a simple graph of order $n\ge 3$. If every pair of distinct nonadjacent vertices $u,v$ satisfies $$ \deg(u)+\deg(v)\ge n, $$ then $G$ has a Hamiltonian cycle. The condition is imposed only on nonadjacent pairs. Ore’s theorem is a standard result; its proof is given in the later treatment devoted to proving the theorem.

The conclusion is that the graph is Hamiltonian; the hypothesis is a sufficient condition for that conclusion, not a characterization. If $G$ is complete, there are no nonadjacent pairs, so the condition is vacuously satisfied. For $n\ge3$, a complete graph has a Hamiltonian cycle: list its vertices in any order and join consecutive vertices, including the last to the first.

Checking the Condition

To test Ore’s hypothesis directly, list the nonedges and compute the degree sum at each one. Adjacent pairs do not need to be checked. If there are no nonedges, the hypothesis holds vacuously; otherwise, every listed sum must be at least $n$. The following examples show why checking actual nonedges can be more informative than comparing the minimum degree alone with $n/2$.

Worked Example: Minimum Degree Below Half the Order

Let $G$ have vertex set $V=\{a,b,c,d,e,x,y\}$. Its edge set consists of all pairs among $\{a,b,c,d,e\}$, together with the edges $xy,xa,xb,yc,yd$. Thus the five vertices $a,b,c,d,e$ form a complete graph, and the other five edges are stated explicitly.

The order is $n=7$. In the complete subgraph, each core vertex initially has degree $4$. The added edges raise the degrees of $a,b,c,d$ to $5$, while $e$ remains at $4$. The two other degrees are $\deg(x)=3$ and $\deg(y)=3$. Therefore $\delta(G)=3$, and $3<7/2$; Dirac’s minimum-degree hypothesis does not apply.

Now check every nonedge. The core vertices are pairwise adjacent, and $xy$ is an edge. The remaining nonedges are $xc,xd,xe,ya,yb,ye$. Their degree sums are $ \deg(x)+\deg(c)=3+5=8$, $ \deg(x)+\deg(d)=3+5=8$, $ \deg(x)+\deg(e)=3+4=7$, $ \deg(y)+\deg(a)=3+5=8$, $ \deg(y)+\deg(b)=3+5=8$, and $ \deg(y)+\deg(e)=3+4=7$. Each sum is at least $n=7$. Ore’s theorem therefore guarantees a Hamiltonian cycle.

One such cycle is $x,a,c,y,d,e,b,x$. Its consecutive pairs are edges: $xa$, $ac$, $cy$, $yd$, $de$, $eb$, and $bx$. It visits all seven vertices exactly once before returning to $x$, verifying the conclusion directly.

Check: The edge count is $10+5=15$: ten edges in the complete graph on five vertices and five added edges. The degree sum is $3+3+5+5+5+5+4=30=2\cdot15$, agreeing with the handshake lemma.

Worked Example: A Second Graph Below Dirac’s Threshold

Let $G$ have vertex set $V=\{a,b,c,d,e,f,x,y\}$. Take every pair among $\{a,b,c,d,e,f\}$ as an edge, and add $xy,xa,xb,yc,yd$. Thus the six core vertices form a complete graph $K_6$, with five additional edges specified.

Here $n=8$. Each core vertex has degree $5$ within $K_6$. The added edges raise the degrees of $a,b,c,d$ to $6$, while $e,f$ remain at $5$. Also $\deg(x)=\deg(y)=3$. Hence $\delta(G)=3<8/2=4$.

The only nonedges are $xc,xd,xe,xf,ya,yb,ye,yf$. Their degree sums are $3+6=9$ for $xc$ and $xd$, $3+5=8$ for $xe$ and $xf$, $3+6=9$ for $ya$ and $yb$, and $3+5=8$ for $ye$ and $yf$. Every one is at least $n=8$, so the graph satisfies Ore’s hypothesis.

A Hamiltonian cycle is $x,a,c,y,d,e,f,b,x$. The edges $xa,ac,cy,yd,de,ef,fb,bx$ are all present, and the cycle contains each of the eight vertices once before returning to its start.

Check: There are $15+5=20$ edges: $K_6$ has $6\cdot5/2=15$ edges, and five edges were added. The degree sum is $3+3+6+6+6+6+5+5=40=2\cdot20$.

How Ore’s Condition Relates to Dirac’s

Dirac’s condition is a uniform lower bound on individual degrees. Ore’s condition is a lower bound on sums, but only for pairs that lack an edge. These hypotheses are related in one direction.

Proposition: If a graph $G$ of order $n\ge3$ satisfies $\delta(G)\ge n/2$, then every pair of distinct nonadjacent vertices $u,v$ satisfies $\deg(u)+\deg(v)\ge n$.

Proof. Assume $\delta(G)\ge n/2$, and let $u,v$ be any distinct nonadjacent vertices. By the definition of minimum degree, $\deg(u)\ge\delta(G)$ and $\deg(v)\ge\delta(G)$. Therefore $\deg(u)+\deg(v)\ge2\delta(G)\ge2(n/2)=n$. This applies to every nonadjacent pair. If there are no such pairs, the assertion holds vacuously. $\square$

Thus Dirac’s minimum-degree hypothesis guarantees Ore’s degree-sum hypothesis. The converse does not hold: in both preceding examples, the Ore condition holds even though the minimum degree is below $n/2$. This does not mean the two theorems have the same hypothesis; it shows that Ore’s test can certify Hamiltonicity in cases where Dirac’s threshold does not apply.

Proposition: If a graph $G$ of order $n\ge3$ satisfies Ore’s degree-sum condition, then $G$ is connected and has no cut vertex. A cut vertex is a vertex whose deletion increases the number of connected components.

Proof. First suppose $G$ is disconnected. Choose vertices $u$ and $v$ from two different connected components of sizes $r$ and $s$. They are nonadjacent. Every neighbor of $u$ lies in its component, so $\deg(u)\le r-1$; likewise $\deg(v)\le s-1$. Since the two components are distinct, $r+s\le n$. Consequently $\deg(u)+\deg(v)\le r+s-2\le n-2<n$, contradicting Ore’s condition. Hence $G$ is connected.

Now suppose $z$ is a cut vertex. The graph $G-z$ has at least two connected components. Choose $u,v$ from two of them, of sizes $r,s$. The vertices $u,v$ are nonadjacent. In $G$, every neighbor of $u$ lies either in its component of $G-z$ or is $z$, so $\deg(u)\le r$; similarly $\deg(v)\le s$. The components are disjoint subsets of $V(G-z)$, which has $n-1$ vertices, so $r+s\le n-1$. Thus $\deg(u)+\deg(v)\le r+s\le n-1<n$, again contradicting the condition. Therefore $G$ has no cut vertex. $\square$

These consequences are useful checks on a proposed example: a disconnected graph or a graph with a cut vertex cannot satisfy Ore’s hypothesis. They do not replace the degree-sum test, since a graph may be connected and have no cut vertex yet still fail that test.

Failure of the Condition Is Not a Disproof

Worked Example: A Hamiltonian Graph That Fails Ore’s Condition

Let $G=C_5$ have $V=\{1,2,3,4,5\}$ and $E=\{12,23,34,45,51\}$. Each vertex has degree $2$, and $n=5$. The nonedges are $13,14,24,25,35$. For each of these pairs the degree sum is $2+2=4$, which is less than $5$. Therefore Ore’s hypothesis fails.

Nevertheless, $1,2,3,4,5,1$ is a cycle containing every vertex, so $G$ is Hamiltonian. This example confirms that Ore’s condition is sufficient but not necessary: failure of its hypothesis leaves the theorem unable to decide Hamiltonicity.

Check: There are five edges, and the degree sum is $5\cdot2=10=2\cdot5$. The listed nonedges account for all $\binom{5}{2}-5=10-5=5$ pairs that are not edges.

Common Pitfall: Doubling the Minimum Degree

A tempting but incorrect shortcut is to check only whether $2\delta(G)\ge n$. In the first example, this calculation gives $2\delta(G)=2\cdot3=6<7$. That tells us Dirac’s hypothesis fails; it does not show that Ore’s hypothesis fails. Ore’s condition asks about each actual nonedge, and in that example the smallest nonedge degree sum is $3+4=7$.

The reverse shortcut is also invalid: checking only one nonadjacent pair does not establish Ore’s hypothesis. Every nonadjacent pair must be checked. For a complete graph there are no such pairs, so the condition holds vacuously; for a graph with nonedges, even one sum below $n$ means the hypothesis is not satisfied. In that case, as the 5-cycle shows, the graph may still have a Hamiltonian cycle.

Check Your Understanding

For each question, distinguish carefully between verifying Ore’s hypothesis and deciding whether a graph is Hamiltonian.

In the first worked example, list all nonedges and their degree sums. Which sum is smallest?
For a graph of order $10$ with minimum degree $5$, show that every nonadjacent pair satisfies Ore’s degree-sum hypothesis.
Let $G$ be a graph of order $8$ with two components of sizes $3$ and $5$. Show that some nonadjacent pair has degree sum at most $6$, so Ore’s condition fails.
Why does the fact that the 5-cycle fails Ore’s condition not contradict Ore’s theorem?
Explain why checking $2\delta(G)\ge n$ is not a valid substitute for checking each nonadjacent pair.