Chapter X Undirected Hamilton Circuit

Tours without arrows

You'd think removing constraints makes problems easier. With Hamilton circuits, it doesn't.

An undirected Hamilton circuit visits every vertex exactly once on a graph with unordered edges. NP-complete (Karp); reduces from the directed version by replacing each directed edge with a small orientation gadget.

There are nice sufficient conditions. Dirac's theorem says every vertex of high enough degree guarantees a Hamilton circuit:

de g (v) \geq \frac{n}{2} for all v \in V ⟹ G is Hamiltonian. (1)

Ore's theorem generalizes (1) to a sum-of-degrees condition over non-adjacent pairs:

de g (u) + de g (v) \geq n for all non-adjacent u, v . (2)

But no efficient necessary condition is known: a graph that fails (1) and (2) might still be Hamiltonian, and detecting non-Hamiltonicity is in general just as hard as deciding Hamiltonicity.

Figures, in plain terms

(1)

deg(v) is the degree of v — the count of edges meeting it. On an undirected graph, no in/out distinction, so just one number.

n/2 is half the vertex count. So the condition demands every vertex has at least half the other vertices as neighbors — a fairly dense graph.

The big arrow ⟹ is implies: if the left side is true, the right side follows. So Dirac's theorem is "high-degree-everywhere implies Hamilton circuit exists."

This is a sufficient condition, not necessary: many sparse graphs are still Hamiltonian. But if your graph passes this test, you can stop checking.

(2)

Ore's condition relaxes Dirac's. Instead of demanding each vertex be high-degree, it demands every non-adjacent pair of vertices have degree-sums of at least n.

deg(u) + deg(v) ≥ n allows individual vertices to be low-degree as long as the deficit is paid by their potential pairing.

for all non-adjacent u, v quantifies only over pairs that aren't already neighbors — the pairs that "could" become a Hamilton-cycle hinge if a clever path closes.

Every graph satisfying Dirac satisfies Ore (so Ore is strictly more general), but Ore graphs not covered by Dirac do exist. Both are sufficient, neither is necessary.