Half the neighbours forces a tour

The symmetric graphs no tour can close ended with a question that has no local test: given a graph, is there a closed tour that passes through every point exactly once? For the Petersen graph the answer was no, for a reason spread over the whole graph rather than visible at any one point, and the essay noted that no simple condition on the points’ neighbourhoods is known to decide the matter in general. Deciding it is NP-complete, one of the problems on Richard Karp’s list of 1972, and no efficient algorithm for it is expected to exist.

That makes it all the more striking that one simple condition does guarantee a tour. Gabriel Dirac proved in 1952 that if a graph has $n \ge 3$ points and every point is joined to at least $n/2$ of the others, then the graph has a closed tour through all of them — a Hamiltonian cycle. The condition can be checked by counting neighbours, and the proof is a pigeonhole argument on a single path. This essay draws that argument, shows why the half cannot be lowered, counts every graph on six points to see how the condition sits among them, and then watches it fail to describe random graphs, where tours are everywhere and the condition almost never holds.

Why a sufficient condition is surprising #

There are two kinds of condition one might hope for. A necessary condition is something every graph with a tour satisfies, so a graph that fails it has no tour; the essay on the Petersen graph used several — every tour contains a perfect matching, and a graph whose removal of a few points leaves too many pieces cannot have one. A sufficient condition is the opposite: anything satisfying it has a tour, and a graph that fails it may or may not.

For a problem as hard as this one, a sufficient condition that is easy to check cannot be close to necessary — if it were, it would nearly decide the problem, and nothing is expected to do that quickly. So Dirac’s condition must be strong, demanding much more than a tour needs. The interest is in how strong. A graph in which every point sees half the others is dense, but not overwhelmingly so: on a hundred points it has at least 2,500 of the 4,950 possible edges, and those edges can be arranged in astronomically many ways. The theorem says none of those arrangements can avoid a tour.

The argument on one path #

Take a path in the graph that is as long as possible — no path visits more points. Call its ends $u$ and $v$, and its points in order $u = p_1, p_2, \dots, p_k = v$.

Because the path cannot be extended, every neighbour of $u$ lies on the path; otherwise $u$’s outside neighbour could be added at the front. The same is true of $v$. So $u$ has at least $n/2$ neighbours among $p_2, \dots, p_k$, and $v$ has at least $n/2$ among $p_1, \dots, p_{k-1}$.

Now look at the $k - 1$ steps of the path, from $p_i$ to $p_{i+1}$. Mark a step above if $u$ is joined to its right end $p_{i+1}$, and below if $v$ is joined to its left end $p_i$. There are at least $n/2$ marks above, at least $n/2$ below, and only $k - 1 \le n - 1$ steps. Some step carries both marks — the pigeonhole principle that more things than boxes made into a method.

That step is the crossing pair the opening figure draws in bold. Delete the step from $p_i$ to $p_{i+1}$, add the edges $u\,p_{i+1}$ and $v\,p_i$, and the path becomes a cycle:

$$p_1 \to p_2 \to \cdots \to p_i \to v = p_k \to p_{k-1} \to \cdots \to p_{i+1} \to u = p_1.$$

The cycle passes through every point of the path. If it missed some point $w$ of the graph, then — because the graph is connected, which the degree condition forces — $w$ would be joined to some point of the cycle, and cutting the cycle open next to that point and attaching $w$ would give a path longer than the longest one. So the cycle covers everything, and it is a tour.

The tour, and the proof as a procedure #

The argument is constructive, and that matters. It does not merely say a tour exists; it says how to find one. Start with any path. If an end has a neighbour off the path, extend. If neither end does, both ends’ neighbours are on the path, and the counting finds a crossing step, closing the path into a cycle; if the cycle misses a point, open it next to that point and extend again. Each round either lengthens the path or turns it into a cycle that is then lengthened, so after at most $n$ rounds of each kind there is a tour. Every step is a scan of neighbour lists.

So the problem that is NP-complete in general becomes, on graphs meeting Dirac’s condition, one that a short procedure solves quickly. That is not a contradiction. The hardness of the general problem lives in sparse graphs, where a longest path’s ends can have few neighbours and no counting forces a crossing — and that is where the procedure has nothing to work with. The move of reversing part of a path to give it a new end is also the engine of the rotation–extension method that the walk through the middle levels used to find tours in a graph far sparser than Dirac allows; there it was a heuristic that happened to succeed, and here it is a proof that cannot fail.

Euler’s easy tour and Hamilton’s hard one #

The contrast that makes the problem famous is with a tour of a different kind. A closed walk that uses every edge exactly once exists in a connected graph exactly when every point has an even number of edges, a fact seven bridges traced to Euler and a walk that splices in its own detours turned into an algorithm. That condition is local, checkable one point at a time, necessary and sufficient at once. Asking instead for a tour through every point exactly once looks like the same question with the words swapped, and it is not: no local condition is both necessary and sufficient, and none is expected, because one would make an NP-complete problem easy.

Dirac’s condition is what a local test can still do in the harder problem. It inspects each point’s degree, like Euler’s test, but it can only ever answer yes; a graph that fails it is returned undecided. The census above measures how often that happens: on six points, four graphs in five that have a tour fail the condition. Euler’s parity test never leaves a graph undecided. The gap between the two problems is exactly the gap between a test that settles everything and a test that settles only the graphs dense enough for a single path to be closed by counting.

Sparse graphs that have tours anyway #

The opposite extreme is just as instructive: graphs far below Dirac’s bound that have tours for structural reasons. The cube in $d$ dimensions has $2^d$ points, each joined to only $d$ others — on ten dimensions, 1,024 points of degree ten, a hundredth of what Dirac asks — and it always has a tour, because a Gray code, the ordering of a walk that changes one thing at a time, is one. The middle levels of the cube are sparser still in proportion, and their tour took decades to establish.

What carries those graphs is symmetry and a recursive construction, not density: a tour of the $d$-cube is built from two tours of the $(d-1)$-cube, joined at the ends. No counting argument of Dirac’s kind could find it, because a longest path’s ends in a sparse graph have too few neighbours to force a crossing. So the landscape has two very different routes to a tour — density, which Dirac’s theorem captures, and structure, which every example of the earlier essays on this subject exploited — and between them a large region, the graphs that are neither dense nor structured, where deciding is genuinely hard. Enough partners in every finite group showed the matching version of the same divide, where Hall’s condition is necessary and sufficient, and that is precisely why matchings are easy and tours are not.

Two graphs one degree short #

The condition is $n/2$. Could it be lowered — to $n/2 - 1$, or to $(n - 1)/2$? Two graphs on seven points say no, and they fail for different reasons.

On the left, every edge runs between the group of three and the group of four. A tour alternates between the groups at every step, so it visits them equally often, and with three on one side and four on the other it cannot. Each point of the four has degree three, which is $(n - 1)/2$. In general the complete bipartite graph with $k$ and $k + 1$ points has smallest degree $k = (n-1)/2$ and no tour: the obstruction is an imbalance.

On the right, two groups of four share a single point. Every point has degree at least three, and the shared point has six. But a tour would have to pass from one group to the other and back, and the only way across is through the shared point, which a tour visits once. The obstruction is a cut point — a single point whose removal disconnects the graph — and it too survives at smallest degree $(n-1)/2$.

So Dirac’s bound is sharp, and sharp in two unrelated ways. That is common for good theorems: the extreme examples are diverse, and a better condition would have to rule out both an imbalance and a bottleneck. Václav Chvátal’s condition of 1972, which looks at the whole sorted list of degrees rather than just the smallest, is the strongest of this kind; it is built precisely to exclude the degree sequences these two examples, and their relatives, have.

Every graph on six points #

To see how the condition sits among graphs in general, take every labelled graph on six points — each of the fifteen possible edges present or absent, $2^{15} = 32{,}768$ graphs in all — and decide for each, exactly, whether it has a tour.

The census confirms the theorem at this size and shows its shape. Graphs with an isolated point or a point of degree one can never have a tour — a point on a cycle needs two neighbours — and those rows are empty. Every graph whose smallest degree is three, four or five has a tour: 1,782, 75 and 1 of them respectively, the last being the complete graph. In between, the graphs of smallest degree two are mostly Hamiltonian, 80.5% of them, and the theorem says nothing about any of them.

The census also tests a refinement. Øystein Ore proved in 1960 that it is enough for every pair of points that are not joined to have degrees adding up to at least $n$ — a condition about pairs rather than single points, and weaker than Dirac’s, since two points of degree $n/2$ always add up to $n$. On six points 1,978 graphs meet Ore’s condition, against 1,858 meeting Dirac’s, and every one of them has a tour. The same crossing argument proves Ore’s theorem, because the argument only ever used the sum of the two ends’ degrees.

Random graphs, where the condition is beside the point #

The census suggests that Dirac’s condition is much stronger than needed. Random graphs make the point dramatic. Join every pair of $n$ points independently with chance one half, and ask two questions: does the graph meet Dirac’s condition, and does it have a tour?

The two shares move in opposite directions. A tour becomes almost certain — 98% of the random graphs on fourteen points have one — while meeting the condition becomes almost impossible: not one of the two hundred graphs on fourteen points has every degree at least seven. The reason is that the average degree of such a graph is $(n-1)/2$, just below $n/2$, and with $n$ points each fluctuating around the average, some point almost always falls short. Dirac’s condition demands that every point clear a bar the average point barely reaches.

What random graphs need for a tour is much less. Béla Bollobás and, independently, János Komlós and Endre Szemerédi showed in the 1980s that a random graph built by adding edges one at a time acquires a tour at exactly the moment its last point acquires a second neighbour — the moment the obvious local obstruction disappears. The moment everything joins up watched the same kind of event for connectivity, which arrives when the last isolated point gets its first neighbour. For random graphs, then, the honest answer to “when is there a tour?” is “as soon as nothing local forbids one”, which is a far weaker condition than half the neighbours — and it is a statement about almost all graphs, which a theorem about every graph cannot be.

What the drawings do not decide #

The tours in the figures are found by exhaustive search over subsets, which decides the question exactly for graphs of up to sixteen points and is useless beyond that; the census and the random-graph shares are exact for the sizes drawn and say nothing directly about larger ones. Dirac’s theorem is what carries the conclusion to every $n$, and the figures check it rather than establish it.

The random-graph figure in particular samples two hundred graphs at each size. Its shares are estimates with a sampling error of a few percentage points, adequate to show the two curves separating and not to measure either precisely. The asymptotic statements — that the chance of meeting Dirac’s condition tends to nought and the chance of a tour to one — are theorems about random graphs, and the figure shows their beginnings at sizes small enough to decide exactly.

And the crossing-pair figure shows one path in one graph. The argument applies to a longest path, and the figure uses a path through all ten points, which is longest automatically; in a graph without a Hamiltonian path the longest path would be shorter, and the argument’s last step — extending through a missed point — would be needed. That step is not drawn, because in a Dirac graph it is never needed at the end: the argument proves the longest path already covers everything.

Still open: degree conditions with a gap #

Dirac’s and Ore’s conditions are about smallest degrees; Chvátal’s about the whole degree sequence; and Chvátal’s condition is, in a precise sense, the best possible condition that looks only at degrees. What remains open lies at the edges of this picture. For graphs with more structure the bounds are expected to drop: Paul Seymour conjectured in 1974 that a graph with smallest degree at least $kn/(k+1)$ contains not just a tour but the $k$-th power of one — a tour in which every point is also joined to the next $k$ points along it — and that was proved only for large $n$, in 1998 by Komlós, Sárközy and Szemerédi, with a threshold so large that the conjecture for all $n$ remains open for $k \ge 2$.

There is also the question of counting. A Dirac graph has not just one tour but many: Gábor Sárközy, Stanley Selkow and Endre Szemerédi showed in 2003 that it has at least $c^n n!$ of them for some constant $c$, and Bill Cuckler and Jeff Kahn found the right constant in 2009. How many tours a graph just failing the condition can have — and whether a single missing degree can destroy all of them at once, as the two graphs above show it can — is understood only in special families.

The half that a single path can see #

The theorem’s proof never looks at the whole graph. It looks at one path and the neighbourhoods of its two ends, and the condition is exactly strong enough that those two neighbourhoods, each covering half the path, must overlap in the one way that closes it. That is why the bound is $n/2$ and not something smaller: below it, two ends can see disjoint halves of the path, as the bipartite example arranges, or both see only their own side of a bottleneck, as the shared point arranges.

So the half is a property of the argument as much as of the graphs. A condition that a single longest path can exploit has to give each end half the graph; a condition that captures what tours really need — as the random graphs show, very little — has to see much more than one path. Between those two lies the whole difficulty of the problem, and the reason that a theorem this easy to state and prove sits beside a problem that nobody can solve quickly.