Lesson 10 ~45 min Introduction to Networks · Path +95 XP

The Königsberg Bridges

In 1736 a Prussian city had a puzzle it could not solve and a mathematician who proved it had no solution. The proof required inventing a way of describing the city that threw away everything except which piece of land connected to which, and that idea is the whole of this focus area.

Today's hook: The people of Königsberg had a Sunday pastime: try to walk a route crossing each of the city's seven bridges exactly once. Nobody ever managed it. Nobody could say why not either, which is a different and more interesting problem.

0/5QUESTS

Think First

warm-up

Before reading on, look at the network in the diagram and apply the rule from Lesson 9. How many vertices have odd degree? What does that tell you?

Record your answer in your workbook.

The Big Idea

+5 XP to read

Königsberg's four land masses become four vertices and its seven bridges become seven edges. The walk everyone wanted is an Eulerian trail, and the degrees decide in one line whether it exists.

$$\deg = 5, \ 3, \ 3, \ 3 \ \Rightarrow \ \text{four odd} \ \Rightarrow \ \text{no trail}$$

The whole difficulty was in the translation. Once the city is a network, the mathematics takes a single line. Euler's achievement was seeing that a question about a city could be a question about four dots.

$\text{four odd vertices}$

Land masses, not bridges, are vertices

The things being connected are the four pieces of land. The bridges are the connections.

Two bridges are two edges

Two pairs of land masses are joined by two bridges each. Collapsing them into one edge destroys the problem.

Impossible is a result

"No such walk exists" is a complete answer, and a stronger one than any route could be.

What You'll Master

objectives

Know

that the Königsberg bridges problem asks for a walk crossing each of seven bridges exactly once
that the problem is modelled by a network with four vertices and seven edges, including two pairs of multiple edges
that the network has four vertices of odd degree, so no Eulerian trail or circuit exists

Understand

why the land masses are the vertices and the bridges are the edges
why the multiple bridges must be kept as separate edges
why proving impossibility is a stronger result than failing to find a route

Can Do

model the Königsberg problem as a network and find the degree of each vertex
apply the degree rule to show that the required walk does not exist
determine how the network would have to change for such a walk to become possible

Words You Need

vocabulary

KönigsbergA Prussian city on the river Pregel, now Kaliningrad, whose bridges gave rise to the problem.

Land massOne of the four pieces of land in the problem: two river banks and two islands.

Multiple edgeA second edge joining a pair of vertices already joined. Two of the bridge pairs are of this kind.

Impossibility proofAn argument showing that no solution exists, as opposed to a failure to find one.

AbstractionDiscarding the features of a problem that do not affect the answer, leaving only what matters.

The City and the Question

+5 XP to read

Königsberg sat on the river Pregel. The river split around an island and then divided again, producing four separate pieces of land: the north bank, the south bank, the large central island, and a further piece of land to the east where the two branches ran together.

Seven bridges joined these pieces. The central island was linked to the north bank by two bridges and to the south bank by two more, together with a single bridge to the eastern land. The eastern land was also joined to each bank by one bridge.

The question the townspeople asked was whether a walk existed that crossed every one of the seven bridges exactly once. Nobody had to start or finish anywhere in particular.

Everyone had tried, and everyone had failed. The interesting mathematical question is not how to succeed but whether success is possible at all.

Stripping It to a Network

+5 XP to read

Euler's insight was that almost nothing about the city matters.

The size of each land mass is irrelevant, since the walk crosses bridges rather than measuring ground. The length of each bridge is irrelevant. So is the shape of the river, the position of the island and the distance between anything and anything else.

What matters is which land masses each bridge joins. So: a vertex for each land mass, an edge for each bridge.

Call the eastern land $A$, the central island $B$, the south bank $C$ and the north bank $D$. Then the edges are two between $B$ and $C$, two between $B$ and $D$, and one each between $A$ and $B$, $A$ and $C$, and $A$ and $D$.

Note what is absent: no edge joins $C$ to $D$, because no bridge runs directly from one bank to the other. Every crossing between the banks goes via the island or the eastern land.

Four vertices and seven edges, and the city is gone. Every question about crossing bridges survives the translation unchanged, and every question about geography has been discarded because it never affected the answer.

Why the Doubles Must Stay

+5 XP to read

Two pairs of land masses are joined by two bridges each. It is tempting to simplify those into a single edge, since either way the two pieces of land are connected.

That would be a serious mistake. The question asks for every bridge to be crossed once, so two bridges are two things to be crossed and must be two edges.

Collapsing them changes the degrees, and it is the degrees that decide the answer. With the doubles kept, the central island has degree $5$; collapsed, it would have degree $3$, and the north and south banks would change too.

A simplification that changes the answer is not a simplification. This is exactly why Lesson 1 introduced multiple edges rather than tidying them away, and the promise made there is being kept here.

The Answer in One Line

+5 XP to read

Count the degrees.

The central island $B$ has five bridges: two to the north bank, two to the south bank, and one to the east. So $\deg(B) = 5$.

Each of the other three land masses has three bridges, so $\deg(A) = \deg(C) = \deg(D) = 3$.

Checking: $5 + 3 + 3 + 3 = 14 = 2 \times 7$, matching the seven bridges.

All four vertices have odd degree. The rule from Lesson 9 says that a connected graph with four or more odd vertices has neither an Eulerian trail nor an Eulerian circuit.

So the walk does not exist, and the townspeople were failing at something impossible. The reason is that each odd vertex would have to be an endpoint of the walk, and a walk has only two ends.

What Euler Actually Achieved

+5 XP to read

Three things happened here that were new, and the third is the one that lasted.

He answered the question. The walk is impossible, which no amount of further attempting could have established.

He replaced a search with a criterion. The argument does not examine routes at all. It counts, and the count applies to every possible route at once, which is why it can prove a negative.

He invented a way of describing shape without measurement. The answer depends on no distance, no angle and no area, only on what is connected to what. Euler called this analysis situs, the analysis of position, and it grew into the subject now called topology. Graph theory, this entire focus area, dates from the same paper.

A local puzzle became a general method. That is a pattern worth recognising, because it is how a good deal of mathematics has actually been made.

Watch Me Solve It · 3 examples

Watch Me Solve It · Modelling the city

+15 XP per step

PROBLEM

Model the Königsberg bridges as a network, stating the vertices and edges, and find the degree of each vertex.

1

Choose the vertices

The objects being connected are the four land masses: the eastern land $A$, the central island $B$, the south bank $C$ and the north bank $D$.
2

List the edges

$AB, \ AC, \ AD, \ BC, \ BC, \ BD, \ BD$

Seven edges, one per bridge. The pairs $BC$ and $BD$ each appear twice, because two separate bridges join the island to each bank. There is no edge $CD$, since no bridge joins the two banks directly.
3

Find the degrees

$\deg(A) = 3, \ \deg(B) = 5, \ \deg(C) = 3, \ \deg(D) = 3$

$A$ appears in $AB$, $AC$ and $AD$. $B$ appears in $AB$, $BC$, $BC$, $BD$ and $BD$, giving five.
4

Check the degree sum

$3 + 5 + 3 + 3 = 14 = 2 \times 7$

The sum matches twice the edge count, so nothing has been missed or double-counted.

AnswerFour vertices with degrees $3$, $5$, $3$, $3$, and seven edges

Watch Me Solve It · Settling the question

+15 XP per step

PROBLEM

Use the degrees to determine whether a walk crossing every bridge exactly once exists.

1

State what is being asked for

A walk crossing every bridge exactly once is a trail using every edge exactly once, which is an Eulerian trail. If it also had to return to its start it would be an Eulerian circuit, but the question allows any finish.
2

Check the graph is connected

Every land mass can be reached from every other across bridges, so the network is connected and the degree rule applies.
3

Count the odd vertices

All four degrees, $3$, $5$, $3$ and $3$, are odd. That is four odd vertices.
4

Apply the rule and conclude

A connected graph has an Eulerian trail only when it has zero or exactly two odd vertices. Four is neither, so no Eulerian trail exists and the walk is impossible. Each odd vertex would have to be an endpoint, and a walk has only two ends.

AnswerNo such walk exists, because the network has four odd vertices

Watch Me Solve It · Changing the city

+15 XP per step

PROBLEM

One of the two bridges between the central island $B$ and the north bank $D$ is removed. Determine whether the walk becomes possible, and if so, where it must start and finish.

1

Update the degrees

$\deg(A) = 3, \quad \deg(B) = 4, \quad \deg(C) = 3, \quad \deg(D) = 2$

Removing an edge lowers the degree of each endpoint by one, so $B$ falls from $5$ to $4$ and $D$ from $3$ to $2$.
2

Check the sum

$3 + 4 + 3 + 2 = 12 = 2 \times 6$

Six bridges remain, and the sum matches.
3

Count the odd vertices

Only $A$ and $C$ are now odd, which is exactly two. The network is still connected, so an Eulerian trail exists running from $A$ to $C$.
4

Produce the walk

$A \to D \to B \to C \to B \to A \to C$

Uses $AD$, $DB$, $BC$, $CB$ (the second bridge), $BA$ and $AC$: six edges, each once. It starts at the eastern land and finishes at the south bank, the two odd land masses, as the rule requires.

AnswerPossible, with the walk running from the eastern land $A$ to the south bank $C$

Brain Trainer · 5 problems

Brain Trainer · Bridges and degrees

5 problems

Five items on the Königsberg problem and its model.

1 In the Königsberg model, what do the vertices represent?

The objects being connected, not the connections.The four land masses
2 How many edges does the Königsberg network have?

One per bridge, with the doubles kept separate.$7$
3 What is the degree of the central island?

Two bridges to each bank, plus one to the eastern land.$5$
4 How many vertices of odd degree does the network have?

The degrees are $5$, $3$, $3$, $3$.$4$
5 Why is the walk impossible?

Each odd vertex would have to be an end of the walk.Four odd vertices, but only two ends

Complete in your workbook.

Multiple Choice · 5 questions

MC1

Setting up the model

+10 XP

In the network model of the Königsberg problem, the edges represent:

MC2

Keeping the doubles

+10 XP

Two bridges join the central island to the north bank. In the model these should be:

MC3

The degrees

+10 XP

The degrees of the four vertices in the Königsberg network are:

MC4

Why it fails

+10 XP

The Königsberg walk is impossible because:

MC5

Making it possible

+10 XP

Removing one bridge between the central island and the eastern land changes the degrees to $2$, $4$, $3$, $3$. The walk then:

Short Answer · 3 questions

Model and settle it

+15 XP

SHORT ANSWER

Set up the Königsberg bridges problem as a network, stating what the vertices and edges represent and listing the edges. Find every degree, verify your degrees against the number of bridges, and determine with reasons whether the required walk exists.

Write your working in your book.

Impossible, not merely unfound

+15 XP

SHORT ANSWER

Explain the difference between "nobody has found a route crossing all seven bridges once" and "no such route exists", and describe what makes Euler's argument capable of establishing the second.

Write your working in your book.

Redesign the city

+15 XP

SHORT ANSWER

The city council wants the seven-bridge walk to become possible. Determine the smallest number of bridges that must be removed, name a bridge whose removal would work, and separately determine what would be needed for the walk to be possible as a round trip returning to its starting land mass.

Write your working in your book.

Stretch Challenge · Counting the ways to fix it

+25 XP

CHALLENGE

The Königsberg network has four odd vertices $A$, $B$, $C$, $D$. Suppose the council may add new bridges anywhere, including alongside existing ones. Work out how many bridges are needed to make an Eulerian circuit possible, count how many different ways there are to choose where they go, and explain why one of the arrangements is different in character from the others.

An Eulerian circuit needs every vertex to have even degree. All four vertices are currently odd, so all four parities must be changed.

Adding a bridge between two land masses raises both their degrees by one, changing the parity of both. Each added bridge therefore fixes at most two odd vertices, so at least $\dfrac{4}{2} = 2$ bridges are needed.

Two is achievable, provided the two new bridges pair up all four odd vertices without overlapping. So the answer is exactly $2$.

Counting the arrangements. The task is to split $\{A, B, C, D\}$ into two pairs. Fix $A$ and choose its partner: there are $3$ choices, namely $B$, $C$ or $D$. The remaining two land masses then form the second pair automatically.

So there are $3$ pairings: $\{AB, CD\}$, $\{AC, BD\}$ and $\{AD, BC\}$. Each gives a valid pair of new bridges and an Eulerian circuit.

The one that is different. Check each pairing against the bridges that already exist. The island $B$ is already joined to both banks and to the eastern land; the eastern land $A$ is already joined to both banks. But no bridge at all joins the north bank $D$ to the south bank $C$.

So the pairings $\{AC, BD\}$ and $\{AD, BC\}$ both consist of building a second or third bridge alongside a crossing that already exists. The pairing $\{AB, CD\}$ is different: it requires a bridge between the two banks, where none has ever been built, spanning the full width of the river rather than one of its branches.

The mathematics declares all three equally good, because a plain network records no distances and cannot see that one of the three new bridges would be far longer and more expensive than any of the others. That limitation was flagged in Lesson 3 and this is it arriving in a concrete decision.

A final observation worth making. Adding two bridges gives a circuit, but adding just one gives a trail, and a trail may be all the council needs if the walk does not have to end where it began. Deciding which requirement is the real one is not a mathematical question, and answering the wrong one carefully is a common way to waste a good analysis.

Quick Review

recap

Land masses are vertices, bridges are edges

Four land masses and seven bridges give four vertices and seven edges, with two pairs of land masses joined by two edges each.

The degrees settle it

The degrees are $5$, $3$, $3$, $3$, summing to $14 = 2 \times 7$. All four are odd, and a trail can have at most two odd vertices, so the walk is impossible.

The doubles must be kept

Two bridges are two things to cross. Collapsing them into one edge changes the degrees and therefore changes the answer, which is the test of an illegitimate simplification.

Impossibility is the achievement

Euler replaced a search with a criterion that applies to every route at once, and in doing so invented a way of describing shape without measurement.

Your Badges

0 of 6

First Steps

3-Day Streak

3 in a Row

Lesson Ace

Stretch Seeker

Daily Warrior

Mark lesson as complete

Tick when you've finished Learn, Practice and the Stretch. Earns +95 XP and +25 coins.

Introduction to Networks (Path) index · Maths subject page