Mathematics & Logic · Games, networks & optimization

Why the shortest delivery route is so hard to find

Ask for a route that visits every place once, instead of every road once, and the easy test disappears. The number of possible tours outruns any computer, which is why real route planners settle for good enough.

4 short lessons · about 22 minutes · 6 sources · updated November 2026

The same four-dot graph with a route covering every edge once and another covering every dot once.

What you will learn

  • Tell a route that visits every vertex once apart from one that uses every edge once
  • Say why one of the two questions is much harder to answer than the other
  • Count the distinct Hamilton cycles in a complete graph with a given number of vertices
  • Halve that count to get the number of distinct route lengths, and say why halving is valid

Lesson 1 of 4 · 6 min

Why visiting every place is harder than every road

Before you readA mail carrier must walk every street once. A delivery driver must stop at every address once. For which job can you tell whether such a route exists just by counting the roads at each junction?

Correct.Not quite. The answer is Walking every street.

It works for walking every street. Counting the roads at each junction settles it, while stopping at every address has no known check like that. This lesson shows why the two jobs differ so much.

A mail carrier has to walk down every street on the round. A delivery driver has to stop at every address and doesn't care which streets get skipped. The two jobs sound alike. As math problems they behave completely differently.

Draw the map as a graph, with the places as dots called vertices and the roads as lines called edges. A route that uses every edge exactly once and ends where it began is an Euler circuit. A route that visits every vertex exactly once and ends where it began is a Hamilton cycle. If it doesn't return to its start, it's a Hamilton path.

The name comes from William Rowan Hamilton. In 1857 he invented a puzzle that asked players to trace a route along the edges of a dodecahedron, a solid with 12 five-sided faces, visiting every corner exactly once. The idea is older than that. As early as the 9th century, Indian and Islamic thinkers asked whether a chess knight could visit every square of a board.

Take a graph with vertices a, b, c and d. The route a to b to c to d and back to a is a Hamilton cycle, because it reaches all four vertices without repeating one. It isn't an Euler circuit, because it never uses the edge from a to c. To keep the two apart, think of the E in Euler as standing for edge.

Check yourselfA closed route through a graph visits every vertex exactly once, but leaves two edges unused. What is it?

Correct.Not quite. The answer is A Hamilton cycle but not an Euler circuit.

Hamilton cycles are about vertices and never repeat one, so leaving edges unused is exactly how they fail to be Euler circuits. An Euler circuit would have to use both of those edges. The route is still a circuit, since it returns to its starting vertex.

The bigger difference is how hard each question is to answer. For an Euler circuit, you count. The number of edges at a vertex is called its degree. If the graph is connected and every degree is even, the circuit exists. That's a quick local check, one vertex at a time.

No count like that is known for Hamilton cycles. Say you're planning a tour of an aquarium that visits each exhibit exactly once. You have to plan several moves ahead. Visit neighboring exhibits in the wrong order and you strand one, which you can then reach only by going back through an exhibit you've already seen. Nothing about the exhibit you're standing at warns you.

Some graphs are easy. In a complete graph, every vertex is joined to every other, so you can visit the vertices in any order and a Hamilton cycle is guaranteed. A graph that is one big loop is easy too. Its single circuit is a Hamilton cycle and an Euler circuit at once. Between those extremes, there's no comparably simple test.

Try to recallWhy is it harder to tell whether a graph has a Hamilton cycle than whether it has an Euler circuit?

In a connected graph, you can tell whether an Euler circuit exists from a local property, the degrees of the vertices, so the check is a quick count. A Hamilton cycle has no comparably simple test. Whether one exists depends on how the whole graph fits together, and a wrong choice early in a route can strand a vertex several moves later.

Every road once is a counting question, settled one junction at a time. Every place once has no known shortcut of that kind. Where every place connects to every other, a route always exists, and the trouble becomes how many there are.

Lessons in this topic

  1. Why visiting every place is harder than every road

    Driving every street once and stopping at every place once sound like the same job. Only one of them has an easy test, and this is where the hard problems start.

    Essentials · 6 min

  2. How many routes visit every place once

    When every place connects to every other, the number of possible tours is a factorial. Ten places already allow 362,880 of them.

    Essentials · 5 min

  3. Why checking every route stops working

    Listing every tour and adding each one up always finds the shortest. Past a couple of dozen stops, no computer could finish the list.

    Deeper · 5 min

  4. Why route planners settle for good enough

    Always heading to the nearest unvisited place plans a route in a handful of steps. See what that shortcut gives up, and why it's often worth it.

    Deeper · 6 min

Three quick stories from this topic

Boston's school bus routes

Boston saved 5 million dollars a year by letting an algorithm plan its school bus routes

The city budgeted 120 million dollars to run its school buses in 2016. A contest the next year brought in a team from MIT, whose route-finding algorithm cut the bill and also trimmed 9,000 kilograms of carbon dioxide from each day's driving.

Why routes are hard to plan

Finding the shortest loop through a set of stops is the traveling salesperson problem. A round of just 20 stops has about 60 quadrillion possible routes.

Good enough, found fast

Nobody checks every route. Planners use methods that find a good route quickly and give up the proof that it is the best one.

Every road, every place

No quick test is known for whether a route can visit every place on a map exactly once

Ask for every road exactly once and the test is easy. You count the roads at each junction, a method that goes back to Euler in 1736. Ask for every place exactly once and nobody has found a fast general method.

How each one fails

In a connected graph, Euler circuits never skip a vertex, so they fail to be Hamilton cycles only by revisiting one. Hamilton cycles never repeat an edge, so they fail to be Euler circuits only by skipping one.

Where the name came from

In 1857 William Rowan Hamilton asked for a route along the edges of a dodecahedron that visits every vertex once. He built it as a puzzle and sold it as the Icosian game.

Sixty quadrillion routes

A delivery round with only 20 stops has about 60 quadrillion possible routes

Fix the starting point and the other 19 stops can be visited in 19 factorial orders. Halve that, because a route and its reverse are the same loop. A computer checking a billion routes a second would need almost two years.

Halve it, once

A tour and its reverse use the same edges and so have the same length. That leaves at most n minus 1 factorial over 2 different lengths to compute.

Ten places

For ten places, nine factorial over two is 181,440 distances. Twenty places give a seventeen-digit number. Each extra stop multiplies the work by roughly the number of stops.

Sources

This topic is part of Where quick math intuition goes wrong, a guided path through related topics.

  • The seven bridges of Königsberg

    Turn a famous walking puzzle into points and lines, then count the bridges at each piece of land to prove the walk impossible without trying a single route.

    4 lessons · 17 min

  • Game theory and the prisoner's dilemma

    Game theory studies choices whose results depend on what others choose. See how two prisoners acting sensibly both end up worse off, what a Nash equilibrium is, and why repeating the game can make cooperation pay.

    4 lessons · 16 min

  • Permutations and combinations

    Count possibilities without listing them. Learn when to multiply choices, when order matters and when it doesn't, and work out why a 6-from-49 lottery ticket has about a 1 in 14 million chance.

    4 lessons · 16 min

  • Sets and Venn diagrams

    A set is a collection with a clear rule for what belongs. Learn union, intersection and complement, draw them as overlapping circles, and use them to count survey answers and build search queries.

    4 lessons · 16 min

  • Linear versus exponential growth

    Linear growth adds the same amount at each step and exponential growth multiplies by the same factor. See why they look alike at first, how decay and compound interest follow the same rule, and where the number e comes from.

    4 lessons · 20 min

  • Newton, Leibniz and the invention of calculus

    Two men built calculus independently in the late 1600s, and their followers fought over the credit for decades. See what each found, what thinkers in Greece and India had done before, and whose notation won.

    4 lessons · 16 min

All mathematics & logic topics · Take the quiz