Math Detours · Grade 6 · Around the corner · 13

Seven bridges of Königsberg

A whole city failed to find a walk across its seven bridges. Euler proved there wasn't one by throwing away the map, and started a new kind of mathematics.

Name ____________________Date ____________

Tonight's idea

In the 1700s the city of Königsberg had a river, two islands and seven bridges. The townspeople had a Sunday puzzle: can you walk around the city crossing every bridge exactly once? Nobody could, and nobody could say why not. Then Leonhard Euler looked at it and invented a whole branch of mathematics to answer no.

His first move was to throw away the map. The land masses became dots (vertices) and the bridges became lines (edges); we will just say dots and lines. What is left is a graph: just dots and connections. The shape of the river, the size of the islands, the length of the bridges, none of it matters. Only who connects to whom.

ABCD A = island
Königsberg as a graph: four land masses, seven bridges. A is the central island.

Now count how many edges touch each dot. That number is the dot's degree. Here is Euler's insight. When your walk passes through a dot, you arrive by one edge and leave by another, using up two. So every dot you pass through, however many times, must have even degree. The only exceptions are where you start and where you finish, which can be odd. So:

Euler's rule. All the dots with edges must form one connected network: you must be able to reach each from the others. With that condition, a walk that uses every edge exactly once exists exactly when the number of odd-degree dots is 0 or 2. If it is 0, you can start at any dot with an edge and you will end where you began. If it is 2, you must start at one odd dot and end at the other.

In Königsberg the degrees are 5, 3, 3 and 3. Four odd dots. No walk.

Watch one: the house

PQRST
Draw this without lifting your pencil or repeating a line.

Degrees: the roof point T has 2. The two upper corners R and S each touch a wall, the floor-to-roof diagonal, a roof line and the top line: degree 4. The two bottom corners P and Q each touch the floor, a wall and one diagonal: degree 3.

Two odd dots, P and Q. So it can be done, but only if you start at one bottom corner and end at the other. Start anywhere else and you will fail every time, which is why this puzzle frustrates people: they start at the roof.

One route: P → Q → S → R → P → S → T → R → Q. Check it off: eight lines, each used once.

Your turn

  1. Write the degree of each dot in the Königsberg graph next to it, and check the total of the degrees is 14. Why must the total always be twice the number of edges?
  2. The city builds an eighth bridge between B and C. Now is a walk possible? Where must it start and end?
  3. Instead, the city demolishes one bridge. Which single bridge could they remove to make the walk possible? Is there more than one choice?
  4. Draw a square with both diagonals (an envelope with no flap). Find the degrees. Can it be traced? Now add the flap (a triangle on top). Can it be traced now?
  5. Draw a five-pointed star in one stroke, the way you normally do. Count only the five points as dots (ignore where lines cross inside). Find the degrees and explain why the one-stroke drawing worked and why you ended where you started.
  6. Design a town. Draw a river with two islands and exactly six bridges so that a walk crossing every bridge once is possible and ends back where it started. Check all the degrees.

Stretch: Euler's other formula

Euler found another gem about shapes. For any convex solid with flat faces (no dents and no holes), count the corners \(V\), the edges \(E\) and the faces \(F\). Then \(V - E + F = 2\). Always.

Check it on a cube. Then on a tetrahedron (a pyramid with a triangular base, four faces in all). Then on a square-based pyramid. Then try a shape nobody told you about, like a prism with a hexagonal end. Does it ever fail?

It even works for a connected graph drawn flat on paper with no crossing lines, if you count the outside region as a face. Connected means you can follow edges from any dot to any other. Try it on the house.

Answers

  1. A: 5, B: 3, C: 3, D: 3. Total 14 = 2 × 7. Each edge has two ends, and each end adds 1 to some dot's degree, so the total is twice the number of edges.
  2. B and C become degree 4. Now only A (5) and D (3) are odd, so the walk exists. It must start at A and finish at D, or the reverse.
  3. Every dot is odd, so removing any one bridge turns its two ends even and leaves exactly two odd dots. All seven bridges work. For example, remove one A–B bridge: then A has degree 4, B has 2, and the walk must run from C to D.
  4. Square with diagonals: all four corners have degree 3, four odd dots, impossible. Add the flap: the two top corners gain a line each and become degree 4, leaving the two bottom corners odd. Now possible, bottom corner to bottom corner, exactly the house.
  5. Five dots, each of degree 2 (two lines meet at each point). All degrees even, so the walk exists from anywhere and must return to its start.
  6. Many answers. One: islands A and B, banks N and S. Bridges A–N, A–S, B–N, B–S, A–B, A–B (two parallel bridges between the islands). Degrees: A 4, B 4, N 2, S 2, all even, so you can start anywhere and return.

Stretch. Cube: \(8 - 12 + 6 = 2\). Tetrahedron: \(4 - 6 + 4 = 2\). Square pyramid: \(5 - 8 + 5 = 2\). Hexagonal prism: \(12 - 18 + 8 = 2\). It does not fail for any convex solid. The house drawn flat: the two diagonals cross, so count the crossing as a dot. Then \(V = 6\), \(E = 10\) (six outer lines plus four half-diagonals), and \(F = 6\) (the roof triangle, four triangles inside the square, and the outside). \(6 - 10 + 6 = 2\).

← PreviousNext: Dice don't lie →