1. How many roads does it take to join four towns?
Call the towns A, B, C and D. Each town needs a road to the other three, so counting from each town gives 3 + 3 + 3 + 3 = 12. But the road from A to B is the same road as the one from B to A, so every road was counted twice. Divide by two and you get 6 roads.
The same reasoning works for any number of towns. If every pair of n towns is joined, each has n − 1 roads, and the total is n × (n − 1) ÷ 2. Five towns need 10 roads and six towns need 15. Mathematicians call a picture where every pair of points is joined a complete graph, and the four-town picture is written K4.
2. Why can't you walk all six roads without repeating one?
Try it with a pencil. However you try, you cannot cover all six roads without repeating one. The answer is that it is impossible, and the reason is hidden in the counts. Look at how many roads meet at each town. In this picture it is 3 at every one of them. Three roads cannot be split into pairs: one is always left over.
The rule that decides these puzzles is this. You can walk every road exactly once only if the roads are all connected in one piece and the number of towns with an odd number of roads is 0 or 2 [1]. Our four towns are all odd, so the count of odd towns is 4. That is neither 0 nor 2, so no route exists. This answers the question in the title; the rest of the article explains why the rule is true and where it came from.
Note that the rule has nothing to do with how long the roads are or how they bend. Only the pattern of which town connects to which matters. That is the big idea behind this whole topic.
3. Why do towns with an odd number of roads cause the trouble?
Imagine you are walking and pass through a town in the middle of your trip. You arrive by one road and leave by another, so each pass through uses up two roads of that town. If you use every road exactly once, the roads of a pass-through town must pair up neatly, so the number of roads there has to be even.
Only two towns can be different. At the town where you start, your first step uses one road with nothing to pair it with, so that town can have an odd number. At the town where you stop, your last arrival works the same way. Everything else must be even. If you start and stop in the same town, then every town is even, and you end up back where you began.
That explains "0 or 2." One more fact comes from simple counting. Add up the roads at all the towns and every road gets counted twice, once at each end, so the total is always even. That means the number of odd towns can never be 1 or 3. It is always 0, 2, 4 and so on, and a picture with exactly one odd town cannot be drawn at all.
All of this shows that having at most two odd towns is necessary. Is it also enough? Euler stated that it is, but he did not give a full proof. According to the Wikipedia article on Eulerian paths, the first complete proof was published in 1873 by Carl Hierholzer, after Hierholzer's death [1]. I could not check that date against a second source, so treat it as reported rather than settled.
4. How did Euler use this idea on the bridges of Königsberg?
Königsberg was a city in Prussia, on the Pregel river. Today it is the Russian city of Kaliningrad. The river divided the city into four pieces of land: two banks and two islands. Seven bridges linked them. A puzzle asked whether a walker could cross each bridge exactly once [2].
Euler's step was to throw away everything except the connections. He pictured each piece of land as a point and each bridge as a line between two points. The shape of the land, the length of the bridges and the route taken on each island do not matter [2]. His paper on this, "Solutio problematis ad geometriam situs pertinentis" ("The solution of a problem relating to the geometry of position"), was written in 1735 and published in 1741. The Euler Archive's record describes it as often cited as the earliest paper in both topology and graph theory [3].
Now count. One piece of land has 5 bridges and the other three have 3 each. All four are odd, so there are 4 odd points, not 0 or 2. Euler's conclusion was that no such walk exists [3]. It is the same situation as our four towns: a map that looks nothing like the road picture turns into a problem with the same answer. The Euler Archive's record describes his paper as reducing the problem to an analysis of the degrees of the vertices on a graph [3]. In graph language, a point is a vertex, a line is an edge, and the number of lines meeting at a point is its degree.
5. What changes if you remove a road, or add a fifth town?
Go back to the four towns and remove just the road between A and B. Now A and B have two roads each, and C and D still have three. Only two odd towns remain, so a route should exist. Here is one: start at C and go C → A → D → B → C → D. That uses all five roads exactly once and ends at D.
Now add a fifth town and join every pair. There are 10 roads, and each town has 4, which is even. So there should be a walk that returns to its start. Number the towns 1 to 5 and go 1 → 2 → 3 → 4 → 5 → 1 → 3 → 5 → 2 → 4 → 1. You use all 10 roads once and finish where you began.
So more towns do not simply make the puzzle harder. With n towns all joined to each other, every town has n − 1 roads. For 3, 5 or 7 towns, that is even, and the walk works. For 4, 6 or 8 towns, it is odd at every town, and the walk fails. Two towns with one road between them is a small special case that works, since it has exactly two odd towns.
Königsberg itself changed too. MathWorld notes that two of the original bridges no longer exist and two others have been merged into one. In the modern layout there is still no walk that crosses every bridge and returns to the start, but there is one that crosses them all if it may end in a different place [4]. The rule gave a yes or no for the old city, and it still gives the right answer for the new one.
6. How can you test the rule yourself?
Draw some shapes on paper: a star, a square with both diagonals, a house outline with a cross inside. For each, mark the points where lines meet, write the number of lines at each, and count the odd ones. Make a prediction first. Then try to trace it without lifting your pencil and see whether you were right. If it works, notice where you started and finished. With two odd points, you must start at one of them.
For a bigger challenge, make a table for complete graphs with 2, 3, 4, 5, 6 and 7 towns. List the number of roads, the number of roads at each town, and whether a walk exists. See if you can spot the pattern before reading the explanation in section 5 again.
To go further, the Euler Archive page lists Euler's original paper in Latin, and the Wikipedia article on the bridges has an account of how his argument works. Reading how someone first solved a problem often shows steps that textbooks leave out.