Maths IA · Modelling · topic 81 of 97
Walk every bridge once: from Königsberg to your city · IB Maths IA idea: guide, sample graph and step-by-step plan
count the degrees first!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.
- ✓ you like a puzzle that turns out to have a rule
- ✓ you would rather prove a result than only quote it
- ✓ you want to apply it to a real place you know
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.
Make it yours: pick one twist
Copying a classic won't show your choices. Pick one of these (or invent your own) and your IA becomes yours.
Swipe for more twists →
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.
→ A real proof, not a recipe. Add the converse: if the degrees are right and the graph is connected, a walk exists.Show that the sum of all degrees is twice the number of edges, so the number of odd vertices is always even.
→ A short counting proof that explains why you never see exactly one or three odd vertices on a map.Write out Fleury's or Hierholzer's method on your graph and say why it never gets stuck.
→ An algorithm you can run by hand, then in code. Compare how many steps each needs as the graph grows.Turn bridges over a river, park connectors or the paths of a campus into a graph, and decide what counts as a vertex.
→ Modelling choices become part of the maths: two bridges between the same banks give a multigraph, not a simple one.If your place has more than two odd vertices, find the fewest repeated or new edges that make a walk possible.
→ Pairing up odd vertices links this to the Chinese postman problem and to shortest paths.On a small graph, count the different Euler circuits, or find how the count changes when one edge is added.
→ Counting rather than existing. Choose a graph small enough to check every walk by hand.Your Maths IA research question: run the check
what is a vertex here?Write your own question first. Then make sure it ticks every box:
- 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.
The model
Land masses become dots, bridges become lines, and the degrees decide everything. Draw the graph of your own place and write each degree beside its dot.
How your Maths IA could be laid out
The usual order for a topic like this, what each part needs to show, and roughly how much of your 12 to 20 pages it takes. The words are all yours.
Why this place or puzzle, what you expect before any theory, and what a walk means here.
Vertices, edges and degrees defined and drawn, with every modelling choice explained.
The handshaking lemma and Euler's condition, each with a proof you can follow line by line.
Your chosen algorithm worked through on a small graph, then on your real one.
The odd vertices, the fewest edges to repeat or add, and how you know it is the fewest.
Your walk traced on an actual map, or an attempt to find a counterexample by brute force.
Back to your aim: what the degrees say about your place, with the numbers.
What the graph ignored (distance, direction, closures), and whether a walker would care.
Where the map, the theorem and the algorithm came from.
What your Maths IA graph could look like
whole numbers: plot dotsMade-up values to show the form of a strong graph: the number of different bridges and the number of odd vertices as a place gains one extra bridge at a time. Yours will look different. example only
- A count against a count, so the points are whole numbers and the axes say what is counted.
- A line is a claim: say whether the fewest extra bridges is exactly half the odd vertices, and prove or test it.
- Extra edges between nearby odd vertices can need more than one new bridge each. Say which case your graph is.
- Plot each place you tested as a point so the reader can see the pattern is not one lucky example.
The maths in action
worked through, not sketched!The graph above was a sketch with made-up numbers. This figure works the idea through from the model itself, so you can see what a finished figure looks like. The source line under it says where every number comes from.
Your game plan
Tick steps off as you go. We'll remember on this device.
0 of 10 done
- Read and predictRead how Euler argued about Königsberg. Before any theory, guess which simple graphs you can trace without lifting the pen.
- Choose the placePick 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 graphMark 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 ruleProve the handshaking lemma, then why a trail needs at most two odd vertices. HL: give the converse as well.
- Build a walkRun 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 mapIf 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 reasonCount the walks, or compare two places, or add distances. Choose the one that helps answer your aim.
- Reflect as you goAfter 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 sendCheck every graph is drawn and labelled, every symbol is defined once and the conclusion answers your aim. Then send your teacher one draft.
The maths you'll use
- Degrees and the handshaking lemma – Show that , 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
Syllabus links
- 1.15Proof by induction, contradiction and counterexampleHL
- 1.6Simple deductive proof
- 3.14Graph theory: vocabulary and types of graphHL
- 3.15Adjacency matrices, walks and transition matricesHL
- 3.16Euler and Hamilton paths, spanning trees, Chinese postman, travelling salesmanHL
- 4.12Designing data collection; reliability and validityHL
Read up first
Data and sources to start from
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.
References to cite
- Euler, L. (1741). Solutio problematis ad geometriam situs pertinentis. Commentarii Academiae Scientiarum Imperialis Petropolitanae, 8.
- Biggs, N. L., Lloyd, E. K., & Wilson, R. J. (1986). Graph theory 1736 to 1936 (2nd ed.). Clarendon Press.
- Wilson, R. J. (2010). Introduction to graph theory (5th ed.). Pearson.
Cite what you actually use, in your own format, and say where each number came from.
Traps to avoid in this Maths IA
double bridges count twice- 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 like this
Delivery rounds: the Chinese postman problem●●○
Shortest route: how good is a quick heuristic?●●○
The cheapest network: spanning trees and Steiner points●●●
This guide shows how a topic like this is usually approached. It is not an IA. Your question, choices, data, analysis and words must be your own: change something, tell your teacher where the idea came from, and follow your school's rules on outside help.