The seven bridges
The Prussian city of Königsberg (today Kaliningrad, in Russia) was built around the river Pregel. In the middle of the river was an island, and further east the river split around another piece of land. Seven bridges connected the four land areas.
The townspeople had a puzzle: is it possible to go for a walk that crosses every bridge exactly once? Nobody could find one, but nobody could explain why not, either. In 1736 the question reached Leonhard Euler, then the leading mathematician in Europe. His answer founded a whole new branch of mathematics.
Euler's insight
Euler's first stroke of genius was realising that almost everything about the map is irrelevant. The shapes of the land, the lengths of the bridges, where exactly they are: none of it matters. All that matters is which land areas each bridge connects. So shrink each land area to a dot and draw each bridge as a line:
Now the puzzle is: is there a trail that uses every edge exactly once? (Recall from Unit 2 that a trail never repeats an edge.)
Euler's second insight was to look at what happens at a vertex in the middle of such a walk. Every time you arrive at a land area by one bridge, you must leave it by a different bridge. So the bridges at that land area are used up in pairs: one in, one out. If you pass through a place several times, you use 2, 4, 6… of its bridges, always an even number.
The only exceptions are the start and the end of the walk. At the start you leave without having arrived; at the end you arrive without leaving. So:
- Every land area that's not the start or the end must have an even number of bridges.
- So at most two land areas can have an odd number of bridges.
In Königsberg, all four land areas have an odd number of bridges (5, 3, 3, 3). Four is more than two. So the walk is impossible, and Euler proved it without trying a single route.
Euler's theorem
An Euler trail is a trail that uses every edge of the graph exactly once. If it ends where it started, it's an Euler circuit. Euler's reasoning, completed by Carl Hierholzer in 1873, gives a complete answer:
Euler's theorem
Let G be a connected graph (ignoring isolated vertices).
- G has an Euler circuit exactly when every vertex has even degree.
- G has an Euler trail that isn't a circuit exactly when exactly two vertices have odd degree. The trail must start at one of them and end at the other.
Recall the handshake lemma from Unit 1: the number of odd-degree vertices is always even. So there are only three cases: 0 odd vertices (circuit), 2 odd vertices (trail between them), or 4 or more (impossible).
The house puzzle
Children have long been challenged to draw this "house" without lifting the pencil or going over any line twice:
Degrees of each corner
A solution, lines in order 1 to 8
Try it.
- Does the complete graph K5 have an Euler circuit? What about K4?
- How many bridges would Königsberg have needed to add (and where) to allow a walk crossing every bridge exactly once? To allow a round trip back to the start?
Show answers
- In K5 every vertex has degree 4 (even), so yes. In K4 every vertex has degree 3 (odd), and four odd vertices is too many: no, not even an Euler trail.
- For a walk: add 1 bridge joining two of the odd areas, e.g. North to South. That leaves only the Island and East odd, so a walk exists from one to the other. For a round trip: add 2 bridges, pairing up all four odd areas, e.g. North–South and Island–East. Then all degrees are even.
Finding the route
Euler's theorem tells you whether a route exists. To actually find one, Hierholzer's method works like this (for a circuit):
- Start anywhere and walk, never reusing an edge, until you get back to the start. With all degrees even you can't get stuck anywhere else: each time you arrive at a vertex there's an unused edge to leave by.
- If some edges are still unused, find a vertex on your circuit that touches one of them. Walk a second loop from there using only unused edges.
- Splice the second loop into the first at that vertex. Repeat until every edge is used.
For a trail with two odd vertices, start at one of the odd vertices; the first walk will end at the other one. This runs in time proportional to the number of edges, so Euler routes are easy to find, even in enormous graphs.
Example: reading DNA
Machines that read DNA chop it into millions of short overlapping pieces. One way to reassemble the original sequence builds a graph in which each short piece is an edge, and the full sequence corresponds to an Euler trail through it. Because Euler trails are easy to find, this approach scales to huge genomes.
The Chinese postman
A postman must walk along every street in his district and return to the post office. If the street graph has an Euler circuit, he can do it without repeating a street. If not, some streets must be walked twice. Which ones, to keep the extra walking as small as possible? This is the Chinese postman problem, named after Mei-Ko Kwan (Guan Meigu), who studied it in 1960.
The recipe for a graph with exactly two odd vertices: find the shortest path between them (Unit 5), and walk it twice. That makes every degree even, so an Euler circuit exists in the expanded graph. With more odd vertices, you pair them up so that the total length of the doubled paths is as small as possible. Councils use this to plan routes for street sweepers, snow ploughs, bin lorries and meter readers.
Try it. In the postman example, the diagonal A–C becomes a busy road with length 9 instead of 5. Now which streets should be walked twice, and what's the total?
Show answer
The shortest route between the odd vertices A and C is now A → B → C or A → D → C, both 4 + 3 = 7 (the diagonal is 9). Walk, say, A–B and B–C twice. The streets total 4 + 3 + 4 + 3 + 9 = 23, plus 7 extra: 30.
Hamilton cycles
Here's a puzzle that sounds almost the same: instead of using every edge exactly once, visit every vertex exactly once.
Definitions
A Hamilton path visits every vertex of a graph exactly once. A Hamilton cycle does so and returns to its start. A graph with a Hamilton cycle is called Hamiltonian.
They're named after the Irish mathematician William Rowan Hamilton, who in 1857 sold a puzzle called the Icosian game: find a round trip along the edges of a dodecahedron (a 12-faced solid with 20 corners) that visits every corner exactly once.
Some graphs clearly have no Hamilton cycle:
In general, a graph with a cut vertex (Unit 2) can never be Hamiltonian. There are also conditions that guarantee a Hamilton cycle, such as this one:
Dirac's theorem (1952)
If a simple graph has n ≥ 3 vertices and every vertex has degree at least n/2, then it has a Hamilton cycle.
In other words, if everyone at a party knows at least half the guests, they can always be seated around a round table so that everyone knows both neighbours. But Dirac's condition is only sufficient, not necessary. A plain cycle C10 has every degree equal to 2, far below 10/2, yet it is obviously a Hamilton cycle itself.
Why Hamilton is hard
For Euler trails we have a perfect test (count the odd vertices) and a fast method to find the route. For Hamilton cycles, nobody knows any efficient method at all. Every known approach, in the worst case, does something not much better than trying an astronomical number of possibilities.
| Euler trail / circuit | Hamilton path / cycle | |
|---|---|---|
| Must use… | every edge exactly once | every vertex exactly once |
| Simple test? | Yes: count odd-degree vertices | No known simple test |
| Fast method to find one? | Yes (Hierholzer) | None known; believed impossible |
| Real-world use | Street sweeping, snow ploughs, DNA assembly | Delivery rounds, drilling circuit boards, touring |
The Hamilton cycle problem is NP-complete. Roughly, that means it's one of a large family of problems (including Sudoku-style puzzles of any size, timetabling and many scheduling problems) that are all equally hard: a fast method for any one of them would give a fast method for all of them. Whether such a method exists is the famous "P versus NP" question, one of the seven Millennium Prize Problems, with a million-dollar prize for its solution. Most experts believe no fast method exists.
The travelling salesman
The weighted version of the Hamilton cycle problem is the travelling salesman problem (TSP): given some cities and the distances between them, find the shortest round trip that visits every city exactly once and returns home.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | – | 16 | 33 | 33 | 17 |
| B | 16 | – | 18 | 25 | 17 |
| C | 33 | 18 | – | 17 | 25 |
| D | 33 | 25 | 17 | – | 18 |
| E | 17 | 17 | 25 | 18 | – |
With 5 cities there are only 12 different round trips (fix the starting city, then there are 4 × 3 × 2 × 1 = 24 orders, but each trip is counted twice, once in each direction). Checking all 12 is easy. But the count grows explosively: 10 cities give 181,440 trips, and 20 cities give about 60 quadrillion.
So people use shortcuts called heuristics, which are fast but not guaranteed to be best. The simplest is nearest neighbour: from wherever you are, go to the closest city you haven't visited yet.
Nearest neighbour from A: 101
The best tour: 86
Nearest neighbour made locally sensible choices that painted it into a corner. Better heuristics improve a tour by repeatedly swapping pairs of edges to remove crossings and detours (a crossing in a tour can always be "uncrossed" to make it shorter). With clever mathematics, researchers have solved instances with tens of thousands of cities exactly, and found near-perfect tours for millions.
Example: where the TSP shows up
Delivery companies plan van routes; factories order the holes a drill must make in a circuit board; telescopes plan the order in which to point at stars; and DNA researchers order fragments. In every case, the travel between stops is wasted time, and a shorter tour saves money.
Practice set
Mixed questions covering the whole unit. Try each one before opening the answer.
1. A connected graph has degrees 2, 2, 4, 4, 6. Does it have an Euler circuit, an Euler trail, or neither?
Show answer
All degrees are even, so it has an Euler circuit.
2. For which values of n does the cycle Cn have an Euler circuit? A Hamilton cycle?
Show answer
All of them, for both. Every vertex has degree 2 (even), and the cycle itself visits every vertex once.
3. For which n does the complete graph Kn have an Euler circuit?
Show answer
Every vertex has degree n − 1, which must be even, so n must be odd (3, 5, 7, …).
4. Does the complete bipartite graph K3,3 have a Hamilton cycle? Does K2,4?
Show answer
In a bipartite graph, a cycle alternates sides, so it uses equally many vertices from each side. K3,3: yes, alternate between the sides (a1, b1, a2, b2, a3, b3, back to a1). K2,4: no, the sides are unequal, so no cycle can include all 6 vertices.
5. A museum has rooms connected by doorways. A guard wants to walk through every doorway once; a visitor wants to see every room once. Which of them has an Euler problem, and which a Hamilton problem?
Show answer
With rooms as vertices and doorways as edges, the guard has an Euler problem (every edge once) and the visitor a Hamilton problem (every vertex once). The guard's question can be answered instantly by counting doorways per room; the visitor's may take real searching.
6. How many different round trips are there through 7 cities (counting a trip and its reverse as the same)?
Show answer
(7 − 1)! ÷ 2 = 720 ÷ 2 = 360.
Summary and glossary
- Euler turned the Königsberg bridges into a graph in 1736: the beginning of graph theory.
- A connected graph has an Euler circuit when every degree is even, and an Euler trail when exactly two degrees are odd.
- Euler routes can be found quickly. When they don't exist, the Chinese postman problem asks which edges to repeat.
- A Hamilton cycle visits every vertex once. There's no known simple test, and the problem is NP-complete.
- The travelling salesman problem asks for the shortest Hamilton cycle. In practice it's attacked with heuristics like nearest neighbour.
- Euler trail
- A trail using every edge exactly once.
- Euler circuit
- An Euler trail that ends where it started.
- Chinese postman problem
- Find the shortest closed walk that uses every edge at least once.
- Hamilton path
- A path visiting every vertex exactly once.
- Hamilton cycle
- A cycle visiting every vertex exactly once.
- Hamiltonian graph
- A graph that has a Hamilton cycle.
- Travelling salesman problem
- Find the shortest Hamilton cycle in a weighted complete graph.
- Heuristic
- A fast rule of thumb that usually gives a good, but not necessarily best, answer.
- NP-complete
- One of a family of problems with no known fast method, all equally hard.