The symmetric graphs no tour can close

The closed walks drawn so far all existed. A walk that changes one thing at a time found a closed tour of every cube, every place changes back counted and sorted them, and the walk through the middle levels found one through the two middle levels of every odd cube, though proving it took thirty years. Each of those graphs is symmetric in the strongest sense: any vertex can be carried to any other by a symmetry of the whole graph, so that standing at one vertex and looking out, the graph looks the same as from any other. Graphs like that are called vertex-transitive, and in 1969 László Lovász asked whether every connected one has a path through all of its vertices.

The obvious guess is that symmetry helps. A graph that looks the same everywhere has no bottleneck, no corner a tour could get stuck in, no region more crowded than another. This essay is about the graphs where the guess fails for closed tours — there are very few of them — and about why it fails in each, which turns out to be visible in the same words of ones and noughts that the cube walks were made of.

Ten words, three neighbours each #

The figure above is Petersen’s graph, built from words. Take the words of length five with exactly two ones — there are ten, one for each pair of places — and join two words when they have no one in the same place. The word 11000 is joined to 00110, 00101 and 00011, the three words whose ones fall in the last three places; every word is joined in the same way to three others. Any rearrangement of the five places carries the set of words to itself and keeps disjoint words disjoint, so the 120 rearrangements are symmetries of the graph, and since any pair of places can be moved to any other pair, every word is like every other. The same construction with $k$ ones in $n$ places gives the Kneser graphs, whose colourings are the subject of the colours a circle forces; Petersen’s is the smallest interesting one.

The graph is drawn in its usual shape: a pentagon outside, a five-pointed star inside, and five spokes between them. The heavy line visits all ten words without repeating, and so is an open tour. Its two ends, marked in red, are not joined, so it cannot be closed into a cycle. That is not bad luck with this tour. An exhaustive search through every way of walking the graph finds 120 open tours, counted once each regardless of direction, and not a single closed one.

Ten vertices is small enough that the search is the proof. But a search says that something is true without saying why, and Petersen’s graph has a short reason that the search does not show.

Every tour leaves out a perfect matching #

In a graph where every vertex has exactly three edges, a closed tour through every vertex enters each vertex along one edge and leaves along another. It uses two of the three edges at each vertex and ignores the third. The ignored edges therefore touch every vertex exactly once: they form a perfect matching, a pairing of all the vertices by edges.

That turns the question round. Instead of searching through tours, search through perfect matchings, and ask whether removing one leaves a single cycle through all ten vertices. Removing a perfect matching from a graph in which every vertex has three edges leaves every vertex with two, and a graph in which every vertex has two edges is a collection of separate cycles. A closed tour exists exactly when for some perfect matching that collection is a single cycle.

Petersen’s graph has exactly six perfect matchings, found by trying every set of five edges. One is the set of five spokes, and removing it leaves the outer pentagon and the inner star, two separate five-cycles. The other five are its images under the symmetries, and each of them also leaves two pentagons. No perfect matching leaves a ten-cycle, so no closed tour exists — an argument over six cases rather than over all the walks.

The same pairing gives a second proof that connects to a different question. A closed tour on ten vertices has ten edges, which can be coloured alternately with two colours; the ignored matching then takes a third. So a graph with three edges at each vertex and a closed tour can have its edges coloured with three colours so that no two edges at a vertex share one. Petersen’s graph cannot be coloured that way — it is the smallest of the snarks, the graphs that resist three edge-colours, which every edge on exactly two cycles meets as the hard case of the cycle double cover conjecture — so it cannot have a closed tour.

The failure is spread over the whole graph #

A graph with no closed tour usually has a reason that can be pointed to: a bridge whose removal splits it, a vertex that splits it, a set of vertices whose removal leaves more pieces than the set has members. Petersen’s graph has none of these. Its symmetry already rules out a special place, and the next figure measures how evenly the failure is spread.

Remove any one word and the remaining nine have closed tours, two of them each time. A graph with no closed tour that gains one as soon as any single vertex is removed is called hypohamiltonian, and Petersen’s graph is the smallest. The obstruction is not a defect anywhere in particular; it is a property of the whole ten-vertex arrangement that disappears as soon as any part of it is missing. That is why searching for a local reason fails and why the six-matching argument works: it is a global count over a structure that the whole graph shares.

It also explains why Lovász stated his question for paths rather than closed tours. Petersen’s graph has open tours in abundance, and so does every other known exception. A conjecture about closed tours would already be false, and the known failures fail only at the last step, between two ends that happen not to be joined.

One size up, the tour closes #

Petersen’s graph is the words with $k$ ones in $2k+1$ places for $k = 2$. Raise both numbers by one and the result is the graph of the thirty-five words with three ones in seven places, joined when disjoint. Each word now has four neighbours, the three-one words in the four places it leaves empty.

A search finds a closed tour quickly, using the same rotations that found tours of the middle levels: extend a path while possible, and when stuck, reverse a stretch of it so that the end moves to a new word with fresh neighbours. These graphs, the words with $k$ ones in $2k+1$ places, are called the odd graphs, and the middle levels are closely related to them, since two disjoint $k$-sets of $2k+1$ places are exactly a $k$-set and the complement of a $(k+1)$-set containing it. Torsten Mütze, Jerri Nummenpalo and Bartosz Walczak proved in 2018 that every odd graph beyond Petersen’s has a closed tour.

The extra place makes the difference, and the matching argument shows how. With four edges at each vertex a closed tour leaves out two at each, not one, and the left-out edges no longer form a matching with a rigid structure. There are far more ways for the remaining edges to join into one cycle, and nothing about the graph’s arithmetic forces them to break into pieces.

Coxeter’s graph: delete seven words #

The thirty-five words with three ones in seven places contain a famous set of seven: the lines of the Fano plane, the geometry of seven points and seven lines in which every two points lie on exactly one line. Number the places 1 to 7; the lines are the words with ones at $\{1, 2, 4\}$ and its six turns, $\{2, 3, 5\}$, $\{3, 4, 6\}$ and so on round the seven places. Delete those seven words from the graph of thirty-five.

What remains is H. S. M. Coxeter’s graph. Each surviving word loses exactly one of its four neighbours, since among the four three-sets disjoint from a non-line exactly one is a line, so every vertex has three edges. The shortest cycle has seven edges, which is unusually long for a graph of twenty-eight vertices. Turning the seven places one step is a symmetry, and it sorts the twenty-eight words into four rings of seven, which is how the graph is drawn. Its full symmetry group, inherited from the symmetries of the Fano plane together with some others, moves any vertex to any other, so it is vertex-transitive.

And it has no closed tour. The exhaustive search that settled Petersen’s graph settles this one too, with one shortcut: a partial walk is abandoned as soon as some unvisited word has fewer than two unvisited neighbours left, since such a word could never be both entered and left. Over every path from a fixed starting word, none closes. W. T. Tutte gave a proof by hand in 1960, and it is considerably longer than the six matchings of Petersen’s case, because the edge-colouring shortcut is not available.

The deletion is the instructive part. The thirty-five words have a closed tour; the seven Fano lines are a fifth of them, removed in the most symmetric way possible, and the closed tour is gone. The two graphs with three neighbours a word that refuse a closed tour are both built from words joined when disjoint, and both fail through the same kind of rigidity.

Every Kneser graph on up to ten places #

The general Kneser graph takes the words with $k$ ones in $n$ places, for any $n$ at least $2k+1$. The figure checks every one on up to ten places.

Every graph has a closed tour except Petersen’s. The graphs grow quickly — 210 words of ten places with four ones — and the search still finds tours easily, because adding places adds neighbours: the words with two ones in ten places have twenty-eight neighbours each, and a graph that dense is easy to tour. The hard cases are the sparse ones, the odd graphs along the top of each column, with $k+1$ neighbours per word, and those were the last to be proved. Arturo Merino, Mütze and Namrata completed the picture in 2023: every Kneser graph except Petersen’s has a closed tour.

So the Kneser family, which contains the most famous symmetric graph without a closed tour, contains no other. The exceptions do not come in families. They come singly, as particular small graphs whose structure happens to make every way of pairing off their edges break the remainder into pieces.

Swelling a vertex into a triangle #

Two of the known exceptions are made from Petersen’s and Coxeter’s graphs by a single operation, and the reason it preserves the failure takes one paragraph. Replace every vertex of a graph with three edges at each vertex by a small triangle, attaching each of the vertex’s three edges to a different corner. The new graph has three times as many vertices, still three edges at each, and it inherits every symmetry of the old one; for Petersen’s and Coxeter’s graphs it is still vertex-transitive.

Suppose the swollen graph had a closed tour. The tour must visit all three corners of every triangle. It can only enter or leave a triangle along one of the three original edges attached to it, and if it entered and left a triangle twice it would need four of those three edges. So it enters each triangle exactly once, walks through all three corners, and leaves by a different original edge. Shrinking each triangle back to a point turns the tour into a closed tour of the original graph, visiting each vertex once. Petersen’s and Coxeter’s graphs have none, so their swollen versions have none either, and the list of exceptions grows from three to five without any new idea.

The same argument shows why the operation does not manufacture new exceptions from graphs that have closed tours: a closed tour of the original graph can be expanded through each triangle the other way, entering one corner, walking the other two, and leaving. Swelling neither creates nor destroys a closed tour; it only multiplies the number of vertices by three.

A question with no local test #

Euler’s question about walks is the mirror image of this one, and the contrast is the reason Lovász’s question is hard. A closed walk that uses every edge once exists in a connected graph exactly when every vertex has an even number of edges, a test that can be checked one vertex at a time, and a walk that splices in its own detours builds the walk by a procedure that never backtracks. For a closed walk that visits every vertex once there is no such test. Every vertex of Petersen’s graph looks exactly like every vertex of the odd graph one size up, as far as anything local can see — three or four neighbours, no short cycles, the same view in every direction — and one has a closed tour while the other does not.

That is the general situation, not a quirk of symmetric graphs. Deciding whether an arbitrary graph has a closed tour is one of the problems that no known method solves substantially faster than trying the possibilities, and the related problem of finding the shortest closed tour through cities, which tours within half again of the best approximates rather than solves, inherits the same difficulty. Symmetry was supposed to be the property that made the question easy, by removing every place where a tour could go wrong. Petersen’s graph shows that it removes the local obstacles and leaves the global one, which is exactly the kind no local test can find.

Five graphs, and a conjecture both ways #

Lovász’s question has had more than fifty years of attention, and the list of connected vertex-transitive graphs known to have no closed tour is short: the single edge joining two vertices, which has no cycle at all; Petersen’s graph; Coxeter’s graph; and the two graphs obtained from these last two by replacing every vertex with a small triangle. All five have open tours, so none is a counterexample to the question as Lovász asked it. And four of the five, all but the single edge, have three edges at each vertex.

The question is asked in both directions. Some believe that every connected vertex-transitive graph has an open tour, and the special case of Cayley graphs — the graphs of a group drawn as a map, in which every connected example is vertex-transitive — is widely conjectured to have closed tours apart from the single edge. Others, László Babai among them, have argued that counterexamples probably exist and that the right expectation is a family of large vertex-transitive graphs with no open tour, found by a construction nobody has yet thought of. The evidence for each side is the same short list: either the exceptions are so rare that they stop at five, or the search has only been looking where tours are easy.

What the searches do not show #

The searches in this essay are complete for the graphs they examine, and for Petersen’s and Coxeter’s graphs they are proofs. For the larger graphs they show only that a tour exists, which a single example establishes, and the table therefore reaches only as far as the theorem of 2023 already did.

What no search can show is the shape of the answer for graphs not yet built. The five exceptions are small, three of them have fewer than thirty vertices, and censuses of the small vertex-transitive graphs, now complete up to several dozen vertices, have been checked without finding more. Small cases have misled this subject before, in both directions, and a counterexample to a statement about every vertex-transitive graph could easily be large.

Still open: whether a sixth exists #

Whether every connected vertex-transitive graph has an open tour is Lovász’s conjecture, and it is open. Whether every connected vertex-transitive graph other than the five above has a closed tour is the stronger form; Carsten Thomassen conjectured that the exceptions are at least finite in number, and that is open too. For Cayley graphs, the conjecture that every one on at least three vertices has a closed tour is open even for some very concrete families, and the known results each cover one class of groups by an argument specific to that class: the commutative groups, groups whose order has few prime factors, and several families of small order.

A more modest question remains about the exceptions themselves. Every known vertex-transitive graph without a closed tour has three edges at each vertex. Whether the property is confined to such sparse graphs — whether, say, every connected vertex-transitive graph with four or more edges at each vertex has a closed tour — is not known either, and the odd graphs, where the jump from three neighbours to four is exactly the jump from Petersen’s failure to a tour, are the best evidence that it might be.