Bridges of Königsberg | FractionRush

🌉 The Setup

Topics: graph theory, nodes, edges, degree, Eulerian paths

The city of Königsberg (now Kaliningrad) sits on a river with two islands. The four land masses are connected by 7 bridges.

Labelling the land masses A (north bank), B (south bank), C (large island) and D (small island):
A–C: 2 bridges | A–D: 1 bridge | B–C: 2 bridges | B–D: 1 bridge | C–D: 1 bridge

Challenge: Is it possible to walk across every bridge exactly once and return to your starting point?

Degree of a node = number of edges (bridges) connected to it.

For an Eulerian path (cross every edge once) to exist:
• A closed loop (start = finish): all nodes must have even degree
• An open path (start ≠ finish): exactly 2 nodes have odd degree

If more than 2 nodes have odd degree, no Eulerian path exists.

Node	Bridges connected	Degree	Odd or Even?
A (north bank)	A–C, A–C, A–D	3	Odd
B (south bank)	B–C, B–C, B–D	3	Odd
C (large island)	A–C, A–C, B–C, B–C, C–D	5	Odd
D (small island)	A–D, B–D, C–D	3	Odd

📝 Questions

Using the bridge connections listed in the setup, count the degree (number of bridges) for each land mass. Fill in the table. 4 marks

Land mass	Bridges	Degree
A (north bank)
B (south bank)
C (large island)
D (small island)

Which land masses have an odd degree? How many of them are there? 2 marks

For an Eulerian circuit (crossing every bridge exactly once and returning to the start), how many nodes with odd degree are allowed? 1 mark

Is the Königsberg bridge walk possible? State clearly and justify your answer using the degree rule. 3 marks

Suppose one bridge between A and C was destroyed (removed). Recount the degrees of all nodes. Is an Eulerian path now possible? (It doesn't need to be a circuit.) 4 marks

Extension: Draw a simple graph (at least 4 nodes) where an Eulerian circuit IS possible. Label the degrees of all nodes and trace the path. 6 marks

Answer Key

🌉 Bridges of Königsberg

1.A: degree 3 (A–C×2, A–D). B: degree 3 (B–C×2, B–D). C: degree 5 (A–C×2, B–C×2, C–D). D: degree 3 (A–D, B–D, C–D).

2.All four land masses — A, B, C, D — have odd degree. There are 4 nodes with odd degree.

3.Zero (for a circuit). Exactly 2 is allowed for an open path (Eulerian trail).

4.Not possible. An Eulerian circuit requires every node to have even degree (so you can always leave a node after arriving). With 4 odd-degree nodes, the walk is impossible — Euler proved this in 1736.

5.Remove A–C: A has degree 2, C has degree 4 — both even. B has degree 3 (odd), D has degree 3 (odd). Now exactly 2 nodes have odd degree (B and D), so an Eulerian trail (start at B or D, end at the other) is possible.

6.Accept any graph where all nodes have even degree (e.g. a square, a cube graph). Award marks for correct degree labels and a valid traced path.