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.

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
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.
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
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.
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.
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.
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.
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
- 12.7 Hamilton Cycles - Contemporary Mathematics, OpenStax, Rice University
- 12.8 Hamilton Paths - Contemporary Mathematics, OpenStax, Rice University
- Euler Paths and Circuits, Oscar Levin, Discrete Mathematics: An Open Introduction
- Hamiltonian path problem, Wikimedia Foundation
- Königsberg Bridge Problem : Wolfram MathWorld, Wolfram MathWorld
- 12.9 Traveling Salesperson Problem - Contemporary Mathematics, OpenStax, Rice University





