Math history · Graph theory

The Seven Bridges of Königsberg

By Melon Tools · 24 September 2026

Can you walk through a city and cross each of its seven bridges exactly once? In 1735 Leonhard Euler proved that in Königsberg you cannot, and the way he proved it became the first theorem of graph theory. The whole argument fits on one page.

Between Stars turns this exact rule into a calm puzzle game for iPhone. Free on the App Store.

Try it first

Here are the four parts of the city and the seven bridges as they stood in 1735. Tap a land mass to start, then tap a bridge or a neighbouring land mass to cross. You may visit a place as often as you like, but no bridge twice.

If you gave up after a few tries, you are in good company: nobody in Königsberg had found a route either. Now tick "Add an eighth bridge" and try again: suddenly there is a route. The reason is the whole story of this page.

The city and its seven bridges

Königsberg in Prussia, today Kaliningrad in Russia, was built on both banks of the river Pregel and on two islands in it. The smaller island, the Kneiphof, held the cathedral. The larger one, the Lomse, lay just to the east, where the two arms of the river meet. Seven bridges joined these four pieces of land:

The question going around was simple: is there a walk that crosses every one of these bridges exactly once? Nobody had found one, but nobody could show that it did not exist either.

How the problem reached Euler

Leonhard Euler was 28 and working at the Academy of Sciences in St. Petersburg. The problem reached him through letters from Carl Leonhard Gottlieb Ehler of Danzig, a friend of the mathematician Heinrich Kühn and later the city's mayor, who had started writing to him in March 1735. Euler did not think much of the question at first. In a letter to Ehler dated 3 April 1736 he wrote:

"Thus you see, most noble Sir, how this type of solution bears little relationship to mathematics, and I do not understand why you expect a mathematician to produce it, rather than anyone else, for the solution is based on reason alone, and its discovery does not depend on any mathematical principle." Leonhard Euler to Carl Ehler, 1736

He took it seriously anyway. He had already presented his solution to the Academy on 26 August 1735 under the title Solutio problematis ad geometriam situs pertinentis, "the solution of a problem relating to the geometry of position". It was printed in the Academy's journal, the Commentarii, in volume 8, dated 1736 but not published until 1741.

Euler's proof, step by step

Euler's first move was the important one. He ignored everything about the map that does not matter: the length of the streets, the shape of the islands, where exactly each bridge stands. All that is left is four regions and which bridges join them. He named the regions with capital letters, A for the Kneiphof, B and C for the two banks and D for the Lomse, and wrote a walk down as the sequence of regions it passes through.

1. Seven bridges mean eight letters

Every bridge you cross takes you from one letter to the next. A walk over one bridge is written with two letters, such as AB. A walk over two bridges needs three, such as ABD. So a walk over all seven bridges is a sequence of exactly eight letters.

2. Count how often each region must appear

Take the Kneiphof, which has five bridges. Each time you arrive or leave, you use one of them. If you pass through it, you use two bridges per visit: one in, one out. With five bridges, which is an odd number, the letter A must appear three times, whether or not your walk starts there. In Euler's words: "since five bridges a, b, c, d, e lead into the island A it is necessary that in the record of crossing by these bridges the letter A shall occur three times." By the same logic, a region with three bridges must appear twice.

3. Add it up

The walk would need nine letters, but seven bridges only allow eight. The walk cannot exist, and that is true for every possible route, not just the ones anyone had tried. (The bridge column adds up to 14, twice the number of bridges, because each bridge is counted once from each of its two ends. Euler pointed that out too.)

The rule Euler found

Euler did not stop at Königsberg. In §20 of his paper he wrote down a rule for any arrangement of regions and bridges:

"If there are more than two regions with an odd number of bridges leading into them, then it can safely be stated that there is no such crossing. And if there are exactly two regions with an odd number of bridges leading into them, then the crossing can be done, provided the walk is started in one of these two regions." Leonhard Euler, Solutio problematis ad geometriam situs pertinentis, §20

In today's language, the regions are vertices, the bridges are edges, and the number of bridges at a region is its degree. A route that uses every edge exactly once is called an Euler path, and if it ends where it started, an Euler circuit.

One detail is often skipped: Euler proved that the condition is necessary, but he only stated that it is also sufficient, meaning that such a route really exists whenever the condition holds. The first complete proof of that half came from Carl Hierholzer and was published in 1873, after his death.

This rule is the Bridges mode in Between Stars. Every level is a star network where you cross each connection exactly once, from 15 tutorial levels to 100 geometric patterns and 101 animal constellations. A solver checks every level before it ships, so unlike Königsberg, each one has a solution.

See both game modes

From a city walk to graph theory

Euler's paper is now usually counted as the first theorem of graph theory and one of the first results in topology, the mathematics of properties that survive stretching and bending. But the field took a long time to form around it:

• 1736: Euler reasons with letters and a single map. There is no dots-and-lines picture in his paper.
• 1847: Johann Benedict Listing publishes Vorstudien zur Topologie, the first printed use of the word "topology".
• 1873: Hierholzer's proof that Euler's condition is also sufficient appears.
• 1892: W. W. Rouse Ball, in his book of mathematical recreations, draws the land masses as points and the bridges as lines, the graph most people picture today.
• 1856: William Rowan Hamilton invents the Icosian game, the puzzle about visiting every point once instead of every line.
• 1936: Dénes Kőnig publishes the first textbook on graph theory.

Today the same ideas route delivery vans, design circuit boards and plan the paths of snow ploughs and street sweepers, which have to drive along every street at least once.

What happened to the bridges

Königsberg was heavily bombed in the Second World War and became the Soviet city of Kaliningrad afterwards. Two of the seven bridges were destroyed in the war, and two more were later replaced by a highway. Five bridges now stand at the historic sites.

That changes the answer. With the present layout, two of the four land masses touch an even number of bridges and two touch an odd number, so by Euler's own rule a walk crossing each bridge exactly once is possible today, as long as you start on one of the two odd ones. The Kneiphof is now a park known as Kant Island, and its cathedral was rebuilt from the 1990s on.

How to solve puzzles like this yourself

Many "draw it in one line" puzzles, from the house-shaped figure children draw without lifting the pen to the levels in Between Stars, are the same problem. Three habits solve almost all of them (there is more practice in our guide to one line puzzles):

1. Count the odd points first. Count the connections at every point. More than two odd points: no solution. Exactly two: start at one of them. None: start anywhere, you will end where you began.
2. Don't burn your bridges. Never use a connection that cuts the unused part of the network in two, unless it is the only one left. This is Fleury's algorithm from 1883, and it guarantees you never get stuck.
3. Leave the dead ends for last. A point with a single connection must be where the route starts or ends. Plan around it early.

Play Euler's puzzle among the stars

Between Stars is a calm puzzle game for iPhone with two modes: Bridges, where you cross every connection once like Euler's walkers, and Starwalk, where you visit every star once like Hamilton's Icosian game. No timers, no ads, undo as often as you like, and every level is solvable.

About the game

Free to download for iPhone with iOS 16 or later. No ads, no subscription.

Questions