Motivation
A route that visits every vertex once asks a different question from an Eulerian route that traverses every edge once. There is no similarly simple degree-parity characterization of Hamiltonian cycles. Degree conditions can nevertheless guarantee their existence. We prove two such conditions and show how to use counterexamples to keep sufficient conditions from being mistaken for necessary ones.
Definitions
Definition 4.1.1
(Hamiltonian paths and cycles)
Throughout, is a finite simple undirected graph with . A Hamiltonian path visits every vertex exactly once. For , a Hamiltonian cycle is a cycle containing every vertex; the starting vertex is repeated only when the cycle is written closed. A graph with such a cycle is Hamiltonian. The minimum degree is for nonempty .
A degree bound such as is a condition on every vertex, not an average-degree condition. In a simple graph the degree of a vertex is at most . The theorem below excludes the cases , where our cycle convention rules out Hamiltonian cycles.
Theorem/proposition
Theorem 4.1.2
(Ore's condition)
Let have vertices. If for every pair of distinct nonadjacent vertices , then has a Hamiltonian cycle.
Corollary 4.1.3
(Dirac's condition)
Let have vertices. If , then has a Hamiltonian cycle.
Proof sketch or proof idea
Proof
(An edge-maximal counterexample and two cross-edges)
First prove Ore's condition by contradiction. Suppose a counterexample exists. Add missing edges one at a time as long as the resulting graph remains non-Hamiltonian. Since there are finitely many possible edges, this stops at an edge-maximal non-Hamiltonian graph ; its degrees remain at least those in , so it still satisfies Ore's condition. It is not complete, because a complete graph on at least three vertices has a Hamiltonian cycle. Choose nonadjacent vertices in .
By maximality, adding creates a Hamiltonian cycle. It must use the new edge, since has none. Removing that edge leaves a Hamiltonian path in from to , say
For , define two sets of indices
They have sizes and : the path lists every other vertex exactly once. Their total size is at least , while there are only available indices, so they intersect. For an index in both, follow the path from to , take the edge , follow the path backwards from to , and take the edge . This is a Hamiltonian cycle in , a contradiction. The index sets automatically exclude the problematic endpoints: is not in because are nonadjacent, and is not in for the same reason.
Proof X-ray
The index intersection closes the path
Ore's condition is used in two separate places. First it must survive the passage from to the edge-maximal graph . It does, because adding edges never lowers a degree, and this is what makes an argument by a maximal counterexample legitimate. Second it is applied to one pair only: the nonadjacent pair whose added edge completes a Hamiltonian cycle. Maximality supplies the spanning path , which the degree hypothesis alone could never produce.
The key move is the shifted indexing in and , which turns one common index into the two cross-edges and ; the count forces such an index. Nonadjacency of and keeps out of and out of , so both cross-edges are genuine edges of . The argument closes by contradiction with the assumption that is not Hamiltonian.
Proof
(Dirac from Ore)
Dirac's condition implies Ore's: every pair of distinct nonadjacent vertices has degree sum at least . If the graph is complete, the statement is immediate; the proof above also handles it because the Ore condition is then vacuously true. The thresholds may be nonintegral, but degrees are integers; for odd , means .
Worked examples
Worked example 4.1.4
(Apply a degree condition)
A simple graph has 8 vertices and minimum degree 4. Dirac's condition applies because , so a Hamiltonian cycle exists. The theorem proves existence without specifying the cycle; finding one is an additional algorithmic task.
Worked example 4.1.5
(A condition can fail while a cycle exists)
The six-cycle is Hamiltonian by definition and has minimum degree 2. Dirac's condition requires minimum degree at least 3, so it does not apply. Failure of a sufficient condition is not proof of failure of the conclusion.
Worked example 4.1.6
(An obstruction by removing a vertex)
Two triangles sharing exactly one vertex have no Hamiltonian cycle. Removing their common vertex disconnects the graph. If a Hamiltonian cycle existed, deleting that vertex from the cycle would leave a path through all other vertices, which would remain connected in the graph after the deletion. The contradiction proves nonexistence.
Common mistakes
Common mistake
(Checking adjacent pairs in Ore's condition)
Ore's condition concerns nonadjacent pairs. Adjacent pairs need not be checked, and if no nonadjacent pair exists the condition is vacuously true.
Common mistake
(Replacing minimum degree by average degree)
A high average degree does not imply a high minimum degree. The clique plus an isolated vertex has and average degree , but it cannot have a Hamiltonian cycle; the same happens for every larger clique plus an isolated vertex.
Common mistake
(Inferring the converse of Dirac's theorem)
Cycles themselves give an infinite family of Hamiltonian graphs whose minimum degree is only two; for this is below . Nor does a sufficient degree condition provide a shortest Hamiltonian cycle or solve a weighted traveling-salesperson problem.
Summary
Ore's condition controls degree sums of nonadjacent pairs; Dirac's stronger minimum-degree condition implies it. The proof turns a maximal counterexample into a spanning path and then uses intersecting index sets to close it. Failure of a sufficient hypothesis leaves the conclusion undecided.
Exercises
Quick check
(A simple graph has vertices and minimum degree . What does Dirac's theorem imply?)
Solution · Answer
Since , the graph is Hamiltonian. The theorem does not identify a specific cycle.
Quick check
(A -cycle has minimum degree . Does the failure of Dirac's hypothesis mean it has no Hamiltonian cycle?)
Solution · Answer
No. The given seven-cycle itself visits every vertex exactly once and is Hamiltonian. Dirac's theorem does not apply, but its converse is false.
Necessary conditions from deleting vertices
A Hamiltonian cycle gives a useful family of necessary conditions.
Proposition 4.1.7
(Deleting vertices from a Hamiltonian graph)
Let be nonempty. If is Hamiltonian, then the graph obtained by deleting and all edges incident with it has at most connected components, counting isolated remaining vertices.
Proof
(Cutting the cycle into segments)
Deleting vertices from a cycle leaves at most path segments. Every remaining vertex belongs to one of those segments, and additional edges of can merge segments but cannot create more components. If , the remaining graph has zero components and the inequality still holds.
The case says that deleting any vertex leaves a connected graph. Thus a Hamiltonian graph has no cut vertex. It also has minimum degree at least two, since each vertex lies on the cycle with two distinct cycle neighbors. These are necessary conditions, but neither alone nor together is sufficient in general. A proof of nonexistence can use them: exhibit a set for which has more than components, or exhibit a vertex of degree at most one. Failure to find such a set does not certify a Hamiltonian cycle.
Worked example 4.1.8
( has no Hamiltonian cycle)
Consider the complete bipartite graph . Remove the two vertices of its smaller side. The three vertices on the other side are isolated, leaving three components, greater than the two vertices removed. Thus has no Hamiltonian cycle. The same conclusion follows from alternation: a cycle in a bipartite graph alternates between the two sides, so a Hamiltonian cycle would use equally many vertices from each side. These are two proofs of the same obstruction, neither based on testing every possible vertex order.
A bipartite graph can still have a Hamiltonian path when its side sizes differ by one. In , label the smaller side and the larger side . The sequence is a Hamiltonian path. It cannot close to a cycle because the endpoints lie in the same side and are not adjacent. Thus a path and a cycle must be distinguished even when both use all vertices.
Sharpness of the minimum-degree threshold
The size of Dirac's threshold is not merely an artifact of rounding.
Counterexample mode
Minimum degree one below the threshold
Claim: for even , minimum degree already forces a Hamiltonian cycle. For even , take two cliques of size and join one chosen vertex of the first clique to one chosen vertex of the second by a single edge. Every vertex has degree at least , but the joining edge is a bridge. A Hamiltonian cycle cannot contain a bridge, because the rest of that cycle would give another path between the bridge's endpoints; and it cannot visit vertices on both sides without using that bridge. Hence the graph is not Hamiltonian. The smallest interesting case is two triangles and joined by the edge : the degrees are , and deleting separates from . The threshold cannot be lowered by one.
For odd , take two cliques of size sharing exactly one vertex and otherwise disjoint. The shared vertex is a cut vertex; deleting it leaves two nonempty components. Each nonshared vertex has degree , and the shared vertex has degree , so the minimum degree is . Again the graph is not Hamiltonian. Together these families show that decreasing the integer threshold by one does not preserve the theorem for all graphs of these orders.
The proof that a bridge cannot lie on a cycle is a local statement: the remaining edges of a cycle form an alternate path around the bridge. In the even-order construction, connectedness forces any spanning cycle to cross between the two cliques, so it would have to use the only joining edge. Both parts of that reasoning are needed.
Constructive interpretation and limitations
Ore's proof can be read backwards. When adding a missing edge creates a Hamiltonian cycle, deleting yields a spanning – path. The degree-sum condition guarantees an index with the two cross edges needed to rearrange the path into a cycle that does not use . For a concrete path, these index sets can be written down and their intersection checked. The proof, however, assumes access to a Hamiltonian cycle in the augmented graph. It is an existence argument as stated; it does not by itself specify a fast method to find that augmented cycle.
For instance, suppose the spanning path is and the graph contains and . Taking gives the cycle . The two cross edges replace the missing closing edge . All six vertices occur exactly once before returning to . This local rearrangement is valid even in a graph that does not satisfy Ore's condition globally; the global condition is what guarantees that some such index exists for the path in the proof.
No efficient general algorithm is known: deciding whether a graph is Hamiltonian is NP-complete.
A natural next question
Is there a fast general test for Hamiltonicity?
No efficient general algorithm is known: deciding whether a graph is Hamiltonian is NP-complete.
Ore’s and Dirac’s conditions are quick to check, but they apply only to fairly dense graphs. For arbitrary graphs, the decision problem “does have a Hamiltonian cycle?” is NP-complete, so a polynomial-time algorithm for it would give one for every problem in NP. None is known. This is why sufficient conditions are paired here with explicit obstructions, such as the vertex-deletion test, rather than with a complete characterization.
Quick check
(A graph has a vertex of degree one. Can it be Hamiltonian?)
Solution · Answer
No under the cycle convention. A Hamiltonian cycle would use two distinct edges incident to every vertex, but a degree-one vertex has only one.
Quick check
(Show that a bipartite graph with unequal part sizes has no Hamiltonian cycle.)
Solution · Answer
A cycle alternates between the two parts, because every edge crosses between them. Returning to its initial vertex requires equal numbers of vertices from each part on the cycle. A Hamiltonian cycle contains all vertices, so the two part sizes would have to be equal.
Quick check
(For the path suppose the extra edges and exist. Give a Hamiltonian cycle.)
Solution · Answer
Choose . The required edges are and . Follow . The middle edges come from the path in reverse order; the two extra edges complete the cycle.
Comparing the two degree tests
Dirac's condition is easier to check from the single number , whereas Ore's condition can succeed even when one vertex has relatively low degree. For example, take and delete two edges that share one endpoint . The vertex has degree 2, below , so Dirac does not apply. Its two nonneighbors each have degree 3, giving degree sum . These are the only nonadjacent pairs, so Ore applies and the graph is Hamiltonian. An explicit cycle is obtained by placing between its two neighbors and joining the remaining two vertices along the complete subgraph.
Checking Ore's condition requires examining nonadjacent pairs and their degree sums. If one pair violates the inequality, the theorem simply gives no conclusion; a Hamiltonian cycle may still exist. Conversely, if all pairs satisfy it, existence is guaranteed even though the theorem does not count the number of different cycles. State the graph order and the degrees used when applying the test, so a reader can verify that all relevant pairs were covered.