IB Maths IA idea · Graph theory and networks

Walk every bridge once: from Königsberg to your city

In 1736 the people of Königsberg wondered whether anyone could cross all seven of the city's bridges exactly once. Euler showed why not with one idea: count how many roads meet at each place.

Graph theory and networks
SL stretch
HL ideal
Maths AI Published data
Syllabus: AA 1.15, AA 1.6

By Photon Academy · Updated 13 November 2026

These ideas are starting points, not an IA to copy. Never copy an idea blindly: make the question, method and analysis your own, and check your plan with your teacher.

The big idea

Draw each land mass as a dot and each bridge as a line between dots. The question becomes: can you trace the whole drawing without lifting your pen or repeating a line? The answer depends only on the number of lines at each dot, its degree. If every degree is even, a closed walk exists; if exactly two are odd, an open one does. Anything else is impossible. Graph theory is AI HL content, so on AI this fits the course; on AA you would be learning a new topic, though the proofs are the kind AA HL students enjoy. The routine part is the rule. The marks come from proving it, showing that the handshaking lemma forces an even number of odd vertices, building a walk with an algorithm, and testing both on a real map.

The maths you will use

Degrees and the handshaking lemma. Show that $\sum \deg v = 2E$ , so the number of odd-degree vertices is even.
Euler's condition. Prove that a connected graph has an Euler circuit if and only if every degree is even, and an Euler trail if exactly two are odd.
Algorithm. Run Fleury's or Hierholzer's method by hand on a small graph and in code on a larger one.
Pairing odd vertices. Add the cheapest set of edges so that all degrees become even, a first step towards the Chinese postman problem.
Proof by induction or contradiction. Prove that a trail leaves a vertex as often as it enters, or that a longest trail must be closed.

Key equations

\sum_{v} \deg(v) = 2E

\text{Euler circuit exists} \quad \text{iff connected and every } \deg(v) \text{ is even}

The maths in action

Left: a river map with a north bank, a south bank, an island and an east land joined by seven bridges. Right: a graph with four vertices and seven edges whose degrees are labelled 3, 3, 5 and 3. — (a) A schematic of the seven bridges of Königsberg. (b) The same map as a graph: the four land masses have degrees 3, 3, 3 and 5, all odd, so no walk crosses every bridge exactly once.

Example research question

To adapt, never to copy

Can every bridge, or every path, of a real place be walked exactly once, and if not, what is the fewest number of repeated or added edges needed, proved from the degrees of the graph and checked on a map?

Change the context, the data or the method so the question is yours. Our Maths IA guide shows how to check it.

Check your research question

Names the place or map and says what counts as a vertex and what counts as an edge.
Says what you will prove or compute: a rule, an algorithm, or the fewest changes to make a walk possible.
Is about a graph with a stated number of vertices and edges that you can draw in full.
Says how you will check the result, for example by trying every walk on a small case.
States what the model leaves out: one-way streets, distances, bridges that no longer exist.

Which course it fits

AA SL not suitable
AA HL stretch
AI SL stretch
AI HL ideal

Syllabus links in Maths AA:

AA 1.15 Proof by induction, contradiction and counterexample (HL only)
AA 1.6 Simple deductive proof

Steps

Read and predict. Read how Euler argued about Königsberg. Before any theory, guess which simple graphs you can trace without lifting the pen.
Choose the place. Pick bridges, park paths or a campus map that you can draw in full with 5 to 12 vertices, and say why that place.
Draw the graph. Mark vertices and edges, count every degree and write the degrees on the drawing. Decide how to treat double edges.
Trial run (1 lesson). Try to trace three small graphs by hand and note the degrees of each. Write what you see before you look up the theorem.
Prove the rule. Prove the handshaking lemma, then why a trail needs at most two odd vertices. HL: give the converse as well.
Build a walk. Run Fleury's or Hierholzer's method on your graph and show each step. Say what goes wrong if you ignore the rule.
Fix a failing map. If your place has too many odd vertices, find the fewest edges to repeat or add, and justify that it is the fewest.
Go further, with a reason. Count the walks, or compare two places, or add distances. Choose the one that helps answer your aim.
Reflect as you go. After every result write one line on what it means for a real walker and what it ignores. These lines become your evaluation.
Cut, check, then send. Check every graph is drawn and labelled, every symbol is defined once and the conclusion answers your aim. Then send your teacher one draft.

Make it yours

Prove the degree rule. Show why a trail passing through a vertex uses edges in pairs, and why the start and end are the only places that can be odd.
Prove the handshaking lemma. Show that the sum of all degrees is twice the number of edges, so the number of odd vertices is always even.
Build the walk by algorithm. Write out Fleury's or Hierholzer's method on your graph and say why it never gets stuck.
Model a real place. Turn bridges over a river, park connectors or the paths of a campus into a graph, and decide what counts as a vertex.
Repair a map that fails. If your place has more than two odd vertices, find the fewest repeated or new edges that make a walk possible.
Count the walks. On a small graph, count the different Euler circuits, or find how the count changes when one edge is added.

HL extension

Prove both directions of Euler's theorem, show the handshaking lemma, and and prove a lower bound on the extra edges needed when a graph has more than two odd vertices.

The data you need

Take a map of a real place (bridges, park paths or a campus) from an online map service, build the graph by hand and count the degrees.

OpenStreetMap

Traps

Treating a double bridge as one edge. Two bridges between the same two banks add 2 to each degree, not 1.
Forgetting that the graph must also be connected. Even degrees alone are not enough if part of the map is cut off.
Counting the degree of a loop as 1. A loop adds 2 to the degree of its vertex.
Quoting Euler's rule without proving it, or proving only one direction of it.
Calling a circuit and a trail the same thing. A circuit must return to the start; a trail need not.
Choosing a place with so many vertices that you cannot check the result by hand.

More Maths IA ideas in Graph theory and networks

Shortest route: how good is a quick heuristic?Free with an account
Deliver to six places and visit each once: how many routes are there, and does the obvious one win? You're going to find out how far off the quick method can be.
Delivery rounds: the Chinese postman problemFree with an account
A newspaper round, a gritting lorry and a street sweeper all have to drive every street, and nobody wants to repeat more than they must. You're going to find the fewest wasted kilometres and prove you cannot do better.
The cheapest network: spanning trees and Steiner pointsIn the Photon IA Guide
To join four towns with the least cable, you might lay a road between neighbours. Add a junction in the middle and the total gets shorter, provided the roads meet at exactly the right angle.
How search engines rank pages: PageRankIn the Photon IA Guide
A page is important if important pages link to it. That sounds circular, and it is, until you write it as one equation and let a matrix settle the argument. You're going to rank a small web, and test what the ranking depends on.
Exam timetables: how few sessions are needed?In the Photon IA Guide
Two subjects cannot sit in the same exam session if a single student takes both. How few sessions can a whole school get away with? You're going to find a lower bound, an upper bound, and close the gap.
Matching students to places: the Gale-Shapley algorithmIn the Photon IA Guide
Every student ranks the schools and every school ranks the students. Can you pair them so that no student and school would both rather swap? Gale and Shapley proved you always can, and gave a method that finds it.