The tour arrives with the last second neighbour

Half the neighbours forces a tour found a condition that guarantees a closed tour through every point of a graph at a glance: if every point is joined to at least half of the others, Gabriel Dirac proved in 1952, the tour exists. The condition is generous. A graph meeting it has more than a quarter of all possible edges, and graphs with far fewer edges have tours too — the boards a knight can tour found them on graphs where each square has at most eight neighbours among hundreds. Dirac’s theorem says when a tour is guaranteed by density. It does not say what the real obstacle to a tour is in a typical sparse graph.

The random graph answers that. The moment everything joins up built a random graph edge by edge and found that it becomes connected at the precise moment its last isolated point gets an edge: the only obstacle to connection, in the end, is a point with no neighbours. This essay asks the same question one step up. A tour needs every point to have at least two neighbours, since it arrives at each point along one edge and leaves along another. Is that the only obstacle? Béla Bollobás proved in 1984, and Miklós Ajtai, János Komlós and Endre Szemerédi independently in 1985, that in the limit it is: the tour appears at the very edge that gives the last point its second neighbour.

Stopping the process at the right moment #

The random graph process starts with $n$ points and no edges, and adds the $\binom n2$ possible edges one at a time in a uniformly random order. After $m$ steps it is a uniformly random graph with $m$ edges, so the process contains every random graph of every density, linked together so that each is a subgraph of the next. Watching a property appear along the process — the way the moment a giant appears watched the largest component swell — is a sharper experiment than sampling graphs at fixed densities, because it records the exact edge at which the property first holds.

For a tour the natural landmark is $\tau_2$, the step at which the last point reaches degree two. Before $\tau_2$ some point has at most one neighbour, and no tour can pass through it. So the tour’s first appearance, $\tau_H$, is never earlier than $\tau_2$, and the question is how much later it comes. The hero shows one process on sixteen points. The 27th edge, dashed, gives point 10 its second neighbour, and at that moment, with only 27 of the 120 possible edges present, the graph already has a tour through all sixteen points: $\tau_H = \tau_2$.

Each graph is decided exactly. For up to eighteen points a dynamic programme runs over the subsets of the points, recording for each subset containing point 0 which points can end a path that starts at 0 and visits exactly that subset; a tour exists if some path through all the points ends at a neighbour of 0. That is $2^{17}$ subsets with a few operations for each point in each, a fraction of a second per graph, and it decides every case — it finds a tour when there is one and proves there is none when there is not. The search reads the tour back from the table, and the hero draws it.

How often the tour is already there #

The theorem is a statement about large graphs, and the figure measures how much of it is already true for small ones. For each number of points from 6 to 18 it runs hundreds of processes, stops each at $\tau_2$, and asks whether the graph there has a tour. At six points the answer is yes 68.5% of the time; at twelve, 75.8%; at eighteen, 80.5%. The rise is slow but steady, and the theorem says it continues to one.

The small sizes are worth taking seriously as they are, not only as a trend. Even at six points, with only fifteen possible edges, two times in three the tour is there the moment the degrees allow it. The degree condition is a very local one — it inspects each point separately — and the existence of a tour is the most global property a graph can have, a single cycle threading everything. That a local condition so often decides a global one, even in graphs this small, is the surprise the theorem makes precise.

It is worth comparing the numbers with what a sampler at a fixed density would see. A random graph on eighteen points with as many edges as $\tau_2$ typically brings has a tour with some probability, but the graphs where it fails are mostly those where some point is short of neighbours. Conditioning on the exact moment that last point is completed removes those failures all at once, and what remains are the rarer graphs where the degrees are all at least two and the tour still does not exist.

When the tour is late #

When the tour is not there at $\tau_2$, the process continues, edge by edge, with an exact search after each, until it is. For twelve points, 97 of 400 processes were late, and the figure counts how late. Twenty-five needed one more edge, twenty-two needed two, twenty-three needed three — seven in ten needed at most three — and the longest wait was eight. The graph at $\tau_2$ is nearly a tour already. What it lacks is not a large structural feature but a small defect, repaired by one or two well-placed edges, and the random process supplies such an edge soon.

This is the shape every proof of the theorem has to exploit. A graph with minimum degree two and a few more edges than that is typically an expander away from its low-degree points — any set of points has many neighbours outside it — and expanders are rich in long paths. The difficulty is concentrated near the points whose degree is exactly two, where the tour has no choice: it must use both of their edges. When several such points are close together, the forced edges can conflict.

The traps near the points of degree two #

The simplest conflict is easy to describe. A point of degree two forces both its edges into any tour. If some point $v$ is joined to three points of degree two, all three forced edges run into $v$, and $v$ would need degree three in the tour — impossible, since a tour gives every point degree exactly two. That is a certificate: a small configuration, checkable at a glance, that proves no tour exists however the rest of the graph looks. A second certificate: two points of degree two joined to each other with a common neighbour. Their forced edges then close a triangle, and a tour on more than three points cannot contain a triangle.

The figure checks every late process for these two traps. About half of the late processes contain one — 66% at eight points, 46% at twelve, 51% at eighteen — and the rest are stopped by larger configurations of the same kind, chains of forced edges that close a short cycle or overload a point by a longer route. All of them sit near the points of low degree. That is the content of the theorem in miniature: in a large random graph the points of degree two are few — their number grows only like $\ln n$ — and far apart, so the chance that two are close enough to interfere goes to nought, and once they are isolated from one another nothing else can stop a tour.

The certificate also explains the slow rise in the previous figure. At eighteen points there are usually several points of degree two at $\tau_2$, crowded into a graph of eighteen, and the chance that two of them share a neighbour is substantial. The theorem’s limit is reached only when $\ln n$ points are scattered among $n$, and the distance between them grows — which happens, but at the pace of a logarithm.

When the last point gets its second neighbour #

The landmark itself has a law. After $m$ edges each point has on average $2m/n$ neighbours, and the number with fewer than two is approximately a Poisson count with mean

$$\lambda(m) = n\left[(1 - p)^{n-1} + (n - 1)\,p\,(1 - p)^{n-2}\right], \qquad p = m \big/ \tbinom n2.$$

So $\tau_2 \le m$ with probability about $e^{-\lambda(m)}$. Writing $m = \tfrac n2(\ln n + \ln\ln n + c)$ makes $\lambda$ tend to $e^{-c}$, and the probability to $e^{-e^{-c}}$: the rescaled waiting time $c$ has a Gumbel distribution, the law of the largest of many independent waits, whose mean is Euler’s constant $\gamma = 0.5772$. Paul Erdős and Alfréd Rényi found this law in 1961 for the minimum degree, and the hitting-time theorem transfers it whole to the tour: the edge count at which a random graph first becomes Hamiltonian has the same limiting Gumbel law as the edge count at which its minimum degree reaches two.

The figure measures $\tau_2$ directly, by running processes on 20 to 1,280 points and recording only the degrees, and plots the average rescaled excess. It does not sit at $\gamma$. It sits near 0.95 at 640 and 1,280 points, with no sign of coming down — and the finite Poisson prediction, computed from $\lambda(m)$ at each actual $n$ without any limit taken, sits right beside it. The limit is approached at a logarithmic pace: the number of points with one neighbour carries a factor $1 + (\ln\ln n + c)/\ln n$, which at 1,280 points is still about $1.3$, and that alone shifts the mean up by a quarter. The measurement agrees with the prediction at every size and disagrees with the limit at every size, which is the correct reading of an asymptotic law.

Euler’s tours need no luck, and Hamilton’s do #

There is an older kind of tour for which the local condition is the whole truth, and the comparison shows how unusual the random-graph theorem is. A walk that uses every edge exactly once and returns home exists precisely when the graph is connected and every point has even degree — Euler’s condition, which the streets a postman walks twice priced and earlier essays proved. That is a statement about every graph, not about typical ones: inspect each point’s degree, check connection, and the answer is certain. No graph meets Euler’s condition and fails to have the walk.

For a walk through every point nothing like that is true. Degree at least two is necessary and wildly insufficient in general — the Petersen graph has degree three everywhere and no tour, and there are graphs of high minimum degree with no tour either, built by joining two large dense pieces through a narrow neck. Deciding whether an arbitrary graph has a tour is one of the original NP-complete problems, and no local inspection could ever decide it. The hitting-time theorem says that randomness restores what Euler’s case has by nature: in a typical sparse graph the necessary local condition becomes sufficient, because the obstructions that defeat it in general — rigid symmetric structures, narrow necks — are vanishingly unlikely to arise by chance.

A count of tours that says nothing #

A tempting shortcut would count the tours. A graph on $n$ points has $(n-1)!/2$ possible tours, and in a random graph with edge probability $p$ each is present with probability $p^n$, so the expected number of tours is $\tfrac{(n-1)!}{2}p^n$. At $\tau_2$, where $p$ is about $(\ln n + \ln\ln n)/n$, that expectation is astronomically large — for eighteen points and the nearly thirty per cent of edges present at $\tau_2$ it is in the tens of thousands — and yet one process in five at that moment has no tour at all.

The first moment fails because tours are not independent: a graph that has one tour typically has a great many, sharing most of their edges, so the expectation is carried by a minority of graphs with enormous numbers of tours while many graphs have none. The same failure appeared in a threshold nobody can place, where the expected number of satisfying assignments of a random formula stays large well past the point where most formulas have none. For tours the failure is total at the threshold: the obstruction is a point of degree one, which makes the count zero in that graph while hardly changing the expectation, and no counting argument that averages over graphs can see a single point’s degree. The proofs that work, through Pósa’s rotations, are about structure rather than counting, and the certificates of the last figure are the structure they have to rule out.

Why a tour is harder than connection, and only a little #

The analogy with connectivity runs deep and fails in an instructive place. For connection, the obstruction at the threshold is an isolated point, and once no point is isolated the graph is connected with high probability, because a disconnected graph with minimum degree one needs a whole small component, and small components are much rarer than isolated points. The argument is a count: there are not enough ways to build a small separate piece.

For a tour no such count suffices, because a graph can fail to have a tour while being well connected — the Petersen graph of the symmetric graphs no tour can close is the famous example, with every point of degree three and no tour at all. What makes random graphs Hamiltonian is a constructive technique, Lajos Pósa’s rotation of 1976. Take a longest path in the graph. If its far end is joined to some point in the middle of the path, the path can be broken there and reversed, giving a new longest path with a new far end. Rotations generate many different far ends, and in a graph that expands — where every set of points has many neighbours — the set of reachable ends is large. Among many ends and many starts some pair is joined by an edge, closing the path into a cycle, or else some end has a neighbour off the path and the path grows. Pósa used this to show that $C\ln n/n$ edges per pair suffice; Komlós, Szemerédi and Alexander Korshunov sharpened it to the exact threshold $(\ln n + \ln\ln n + \omega)/n$; and the hitting-time version followed.

The rotations are a search, and they are what the walk that changes one thing at a time and the knight’s tours did by construction on special graphs. In a random graph the search succeeds for structural reasons — expansion — that hold everywhere except near the points of degree two, which is why those points are where the certificates of failure live.

What the computations show and what they cannot #

The tours and their absence are exact for every graph searched: the subset programme decides Hamiltonicity with no heuristics up to eighteen points, and the hero’s tour is read from its table and checked edge by edge. The shares and histograms are averages over seeded random processes, hundreds at each size, and their error bars are drawn. The degree times to 1,280 points are exact simulations of the process, and the Poisson prediction is computed from an exact formula for the expected number of low-degree points, not from its limit.

Nothing here reaches the theorem’s limit. At eighteen points one process in five still has no tour at $\tau_2$, and the theorem says that share tends to nought without saying how fast; the figures show it falling slowly, consistently with a rate like $1/\ln n$, but a rate cannot be read off seven points of a curve. The search also cannot go much beyond eighteen points with certainty, since the programme doubles in cost with each point, and the backtracking search that handles larger graphs can find tours quickly but proves their absence only slowly. The classification of failures counts two specific certificates and leaves the rest as “larger”: it does not enumerate every obstruction, only shows that the simplest ones already account for half.

Still open: tours in random regular and random geometric graphs #

For the Erdős–Rényi process the story is complete, down to the hitting time. Other models of random graphs pose the same question without the same answer. In a random graph where every point has exactly $d$ neighbours, tours exist with high probability for every $d \ge 3$ — Robert Robinson and Nicholas Wormald proved it in the 1990s — but the proof is a delicate second-moment computation, and the number of tours, while known asymptotically, is not understood well enough to say how the tours are distributed. In a random geometric graph, where points are scattered in a square and joined when close, the hitting-time theorem holds too, but proving it took until 2011, and the analogous statements for higher minimum degree and for more general properties are still being settled.

And there is a finite question the figures raise and do not answer. The share of processes with a tour at $\tau_2$ is 80.5% at eighteen points, and the asymptotic theory predicts the eventual approach to one but gives no formula for the share at any finite $n$. An expansion of that share in powers of $1/\ln n$, with the certificates of the last figure as its first terms, would turn the theorem into a prediction for the graphs anyone can draw, and it has not been written down.

Two neighbours each, and then a tour #

Add the edges between $n$ points in a random order and a tour through every point cannot appear until the last point has two neighbours — and in a large random graph it appears exactly then. Already at six to eighteen points the tour is there at that moment two to four times in five, decided exactly by a search over subsets; when it is late it is late by a few edges, and half the time the culprit is a point with three neighbours of degree two, a trap the tour cannot pass. The moment itself follows a Gumbel law with mean Euler’s constant in the limit, and at a thousand points it is still a quarter of a unit away, exactly where the finite Poisson count says it should be.