In the 1600s the city of Königsberg sat on both banks of a river that split it into four pieces of land: two banks and two islands. Seven bridges joined them, and the people who lived there had a puzzle. Can you take a walk that crosses every bridge exactly once?

Try it and you always get stuck with one bridge left over, wherever you start. In 1735 the mathematician Leonhard Euler proved that nobody could ever do it, and his proof started a new branch of mathematics: graph theory. By the end of this lesson you will be able to give the same proof yourself, in one sentence.

A puzzle by post1:16

The puzzle reached Euler by letter. Carl Ehler, the mayor of Danzig, another city on the Baltic coast, wrote to him about it. Euler was 28 and worked at the Academy of Sciences in Saint Petersburg, then the capital of Russia.

At first he was not impressed. He wrote back (3 April 1736) that the solution had little to do with mathematics, and that he did not see why anyone would expect a mathematician to find it rather than anyone else. Yet the puzzle held his attention, because it was not about lengths or angles, the usual business of geometry. Only position mattered: what is connected to what.

Decades earlier, Gottfried Leibniz had called for exactly that, a new geometry of position (geometria situs). Euler opened his paper with Leibniz's idea and offered the bridges as its first example. He presented it to the Academy in 1735, and it was printed in 1741 under the Latin title Solutio problematis ad geometriam situs pertinentis: the solution of a problem relating to the geometry of position.

Euler's own drawing has no dots and lines. He named the land with capital letters A to D and the bridges with small letters a to g. The dots-and-lines picture came much later, but the idea behind it, keeping only what connects to what, is already in his paper.

Euler's Fig. 1 from the Solutio, with the later dots and lines drawn over it.

From a map to a graph2:40

Euler's first move was to throw away almost everything on the map. The shape of the island does not matter. The length of a bridge does not matter. Only one thing matters: which piece of land is connected to which.

So each piece of land becomes a dot, and each bridge becomes a line between two dots. Königsberg turns into four dots and seven lines. That picture is called a graph.

Euler keeps only the connections: which piece of land touches which bridge.

The same step works almost everywhere. Cities and the roads between them, people and their friendships, web pages and the links between them: each is a set of things plus a set of connections. Once a problem is drawn this way, every tool in graph theory applies to it, whatever the dots and lines originally meant.

What is a graph?3:21

A graph has two ingredients:

• Vertices (one of them is a vertex): the dots.
• Edges: the lines. Each edge joins two vertices.

Mathematicians write a graph as G = (V, E), where V is the set of vertices and E is the set of edges. Here is the graph we use for the rest of the lesson: seven vertices, A to G, and eight edges.

The running example: seven vertices and eight edges.

One idea is easy to miss: the drawing is not the graph. Move the vertices anywhere you like, bend the lines, let them cross. As long as the same pairs are joined, it is the same graph. Everything we prove below depends only on the list of pairs, never on the picture.

Three key words4:04

Three words come up constantly.

• Two vertices joined by an edge are adjacent. B and D are adjacent. A and D are not, because no edge joins them.
• An edge is incident to the two vertices at its ends. The edge BD is incident to B and to D.
• The neighbours of a vertex are all the vertices adjacent to it. The neighbours of D are B, E and F, written N(D) = {B, E, F}.

A useful way to keep the first two apart: adjacent links a vertex to a vertex, incident links a vertex to an edge.

Degree4:38

The most useful number in this lesson is the degree of a vertex, written deg(v): the number of edges that touch it. Counting in our graph:

Each vertex labelled with its degree.

A vertex of degree one is called a leaf, like the tip of a branch. G is a leaf.

The handshake lemma5:02

Add up all seven degrees: 2 + 3 + 3 + 3 + 2 + 2 + 1 = 16. The graph has 8 edges, and 16 is exactly twice 8. This is not a coincidence. It holds for every graph, and it is called the handshake lemma:

Why it is true. Every edge has two ends, and each end adds one to the degree of the vertex it touches. So when you add up the degrees, you are counting edge ends, and every edge contributes exactly two of them. This trick of counting the same thing in two different ways is called double counting, and you will meet it again and again.

Each edge is counted once from each end.

The name comes from a party. Every handshake uses two hands, so if everyone counts the hands they shook, the total is always twice the number of handshakes.

The lemma is also a practical check. If you ever store a graph and the degrees add up to an odd number, the data is wrong before you have run a single algorithm.

Odd vertices come in pairs5:55

The lemma has a surprising consequence:

In our graph the odd vertices are B, C, D and G: four of them.

Why. The total of all degrees is even, because it is twice the number of edges. Split that total into the even degrees and the odd degrees. The even ones add up to an even number, so the odd ones must add up to an even number too. A sum of odd numbers is even only when there is an even count of them.

This settles puzzles without trying a single arrangement. Can seven people at a party each shake hands with exactly three others? That would make the degrees add up to 7 × 3 = 21, an odd number, which can never be twice the number of handshakes. The party is impossible.

Solving the seven bridges6:40

Now we can solve the bridges. As a graph, Königsberg has four vertices. The island Kneiphof has five bridges, so its degree is 5; the other three pieces of land have degree 3. (Some pairs of land are joined by two bridges, so this graph has repeated edges. Graphs like that are the subject of the next lesson.)

Think about the walk. Each time you arrive on a piece of land in the middle of the walk, you must leave it again, so its bridges are used in pairs: one in, one out. Every piece of land therefore needs an even degree, except the place where the walk starts and the place where it ends.

So a walk that crosses every bridge exactly once can have at most two odd vertices. Königsberg has four. Here is the whole proof in one sentence:

Königsberg as a graph: all four vertices are odd.

Euler's own proof counted letters instead. Write a walk as the list of lands you stand on: seven crossings make a list of eight letters. In his naming, A is the island Kneiphof, B the south bank, C the north bank and D the island Lomse. A has five bridges, and each visit uses two of them (one in, one out) unless the walk starts or ends there, so A must appear three times. B, C and D have three bridges each, so each must appear twice. That is 3 + 2 + 2 + 2 = 9 letters, but the list only has room for 8. The walk cannot exist.

Euler's count: nine letters for a list of eight.

Notice what Euler did. He did not try every route. He found a rule that every route must obey and showed that the city breaks it. That is how many proofs in graph theory work.

Euler also went beyond Königsberg. His paper gives a rule for any river with any islands and bridges: if more than two regions have an odd number of bridges, no such walk exists; if exactly two are odd, start at one and finish at the other; if none are odd, you can start anywhere. He claimed that whenever the counts allow it a walk really exists, but he never proved that part. The proof came from Carl Hierholzer and was published in 1873, two years after Hierholzer died.

Today the city is called Kaliningrad, and five bridges stand on the old sites. Now only the two islands have odd degree, so the walk exists, starting on one island and ending on the other. (We showed that such a walk needs at most two odd vertices. Lesson 3 shows that, in a connected graph, that condition is also enough.)

Naming the graph9:18

For more than a century nobody called these pictures graphs. The word arrived in 1878, from the English mathematician James Joseph Sylvester, who borrowed it from chemistry: diagrams of atoms joined by bonds had just become popular, and a molecule is a graph whose vertices are atoms and whose edges are bonds.

Benzene as a graph: atoms are vertices, bonds are edges.

The first textbook on graph theory came out in 1936, written by the Hungarian mathematician Dénes Kőnig, and it gathered scattered puzzles like Königsberg into one subject. Today graphs describe road networks, molecules, friendships and the internet itself, and every one of them starts with Euler's move: keep only what connects to what.

Key ideas10:08

• A graph is a set of vertices and a set of edges joining pairs of them. The drawing does not matter, only which pairs are joined.
• Adjacent: vertex to vertex. Incident: vertex to edge. N(v): the neighbours of v.
• The degree of a vertex counts the edges that touch it, and the degrees always add up to twice the number of edges.
• So the odd vertices always come in pairs, and a walk that crosses every edge once can have at most two of them.

Check yourself

1. A graph has vertex degrees 3, 3, 2, 2 and 2. How many edges does it have?

2. Can a graph have degrees 3, 3, 3 and 2?

3. Suppose Königsberg had built one more bridge, between the north and south banks. Could you then cross every bridge exactly once?

Practice on the platform10:31

The introduction to graph theory guide covers every idea from this lesson with the same example graph. Then open the visualizer, build a small graph of your own and check the handshake lemma on it. For instance, five vertices and six edges with degrees 3, 2, 3, 2 and 2: they add up to 12, twice the number of edges.