Activity: The Seven Bridges of Königsberg

The old town of Königsberg has seven bridges:

Map of Königsberg showing seven bridges connecting four land areas across the river

Can you take a walk through the town, visiting each part of the town
and crossing each bridge only once?

This question was given to a famous mathematician called Leonhard Euler... but let's try to answer it ourselves!

And along the way we'll learn a little about Graph Theory.

Simplifying It

We can simplify the map above to just this:

Simplified schematic of four green landmasses connected by seven blue bridge lines

There are four areas of the town - on the mainland north of the river, on the mainland south of the river, on the island and on the peninsula (the piece of land on the right)

Let's label them A, B, C and D:

To "visit each part of the town" you should visit the points A, B, C and D.

And you should cross each bridge p, q, r, s, t, u and v just once.

Schematic of Königsberg with land areas labeled A to D and bridges labeled p to v

And we can further simplify it to this:

Network graph with four red vertices labeled A through D connected by seven edge lines

So instead of taking long walks through the town,
you can now just draw lines with a pencil.

Your Turn

Can you draw each line p, q, r, s, t, u and v only once, without removing your pencil from the paper (you may start at any point) ?

Have a try and see if you can.

...

Did you succeed?

Well ... let's take a step back and try some simpler shapes.

Try these (remember: draw all the lines, but never go over any line more than once, and don't remove your pencil from the paper.)

Eight geometric graph shapes numbered 1 to 8 for pencil tracing practice

Put your results here:

Shape	Success?
1	Yes
2
3
4
5
6
7
8

So, How Can We Know Which Work and Which Don't?

Let's investigate!

But first, time to learn some special words:

A point is called a vertex (plural vertices)
A line is called an edge
The whole diagram is called a graph

Triangle graph pointing out a vertex, an edge, and the full graph

Yes, it is called a "Graph"... but it is NOT this kind of graph:

They are both called "graphs".
But they are different things. Just how it is.

Coordinate line plot of temperature over days, contrasted with a network graph

Two vertices showing incoming edges with degree 3 and degree 2 labels

The number of edges that lead to a vertex is called the degree

Diagram comparing an Euler path across edges and a path across vertices

A route around a graph that visits every edge exactly once is called an Euler path (or Eulerian trail)
A path that simply never repeats any vertex is called a simple path
A route that visits every vertex exactly once is called a Hamiltonian path

Examples:

House-shaped graph diagram 7 with vertices A, B, C, D, and E

House-shaped graph diagram 8 with center vertex F and outer vertices A to E

Diagram 7 has

5 vertices: A, B, C, D and E
8 edges: AB, BC, CD, DA, AE, BE, AC and BD
Vertices A and B have degree 4
Vertices C and D have degree 3
Vertex E has degree 2

Diagram 8 has

6 vertices: A, B, C, D, E and F
10 edges: AB, BC, CD, DA, AF, BF,CF, DF, AE and BE
Vertices A, B and F have degree 4
Vertices C and D have degree 3
Vertex E has degree 2

Euler Path

OK, imagine the lines are bridges. If you cross them once only, and in one single path, you have solved the puzzle, so ...

... what we want is an "Euler Path" ...

... and here's a clue to help you: we can tell which graphs have an "Euler Path" by counting how many vertices have an odd degree.

So, fill out this table:

Shape	Euler Path?	Vertices	how many with even degree	how many with odd degree
1	Yes	4	4	0
2
3
4
5
6
7
8

Is there a pattern?

...

Look at the shapes where you succeeded. How many odd vertices did they have?
Look at the shapes where you failed. What do you notice about their odd vertices?

Can you spot the rule before scrolling down?

...

OK, the answer is:

The number of vertices of odd degree must be either zero or two.

If not then there's no "Euler Path"

And if there are two vertices with odd degree, then they are the starting and ending vertices.

And the reason isn't hard to understand.

A path leads into a vertex by one edge and out by a second edge.

So the edges should come in pairs (an even number).

Only the start and end point can have an odd degree.

Now Back to the Königsberg Bridge Question:

Network graph with four red vertices labeled A through D connected by seven edge lines

Vertices A, B and D have degree 3 and vertex C has degree 5, so this graph has four vertices of odd degree. So it does not have an Euler Path.

We have solved the Königsberg bridge question just like Euler did nearly 300 years ago!

Bonus Exercise: Which of the following graphs have Euler Paths?

Six practice network graphs numbered 9 through 14

Shape	Euler Path?	Vertices	How many with even degree	How many with odd degree
9
10
11
12
13
14

Footnotes

Portrait of Swiss mathematician Leonhard Euler

Leonhard Euler (1707 - 1783), a Swiss mathematician, was one of the greatest and most prolific mathematicians of all time.

Euler spent much of his working life at the Berlin Academy in Germany, and it was during that time that he was given the "The Seven Bridges of Königsberg" question to solve that has become famous.

The town of Königsberg straddles the Pregel River. It was formerly in Prussia, but is now known as Kaliningrad and is in Russia. Königsberg was situated close to the mouth of the river and had seven bridges joining the two sides of the river and also an island and a peninsula.

Answer to the diagrams table:

Shape	Success?	evens	odds
1	Yes	4	0
2	Yes	2	2
3	NO	0	4
4	NO	1	4
5	Yes	2	2
6	Yes	3	2
7	Yes	3	2
8	Yes	4	2