What can dots and lines tell us?
Can you cross every bridge exactly once? What is the quickest route through a network? How many colours do you really need to colour a map? Graph theory turns questions like these into mathematics using one remarkably simple idea: dots connected by lines.
How to use this course
There’s no need to rush. This course is designed to be explored by thinking, drawing, experimenting and trying things out.
When you reach a problem, have a go before opening the answer — even if you’re not sure where to start. Getting stuck for a while can be useful.
Look out for the 💡 icons. Click one if you’d like a suggestion about how to approach a problem or get more from an idea. They’re completely optional, so confident learners can simply ignore them.
When you meet a new definition, try making up your own examples — and something that is almost an example but fails in one important way.
If you’re working alongside a learner, try asking questions such as “What have you noticed?” or “What could you try next?” before offering an answer.
Stopping with an interesting question still in your head is a perfectly good place to finish.
The six lessons
What is a graph?
Meet vertices, edges and degrees, and discover the basic language of graph theory.
The Bridges of Königsberg
Explore Euler’s famous puzzle and discover when a route using every edge is possible.
Paths, cycles and Euler trails
Learn different kinds of routes through a graph and build your own.
Drawing without lifting your pencil
Use vertex degrees to solve one-stroke drawing puzzles.
Colouring maps
Turn maps into graphs and investigate how few colours are really needed.
Networks and shortest paths
Use weighted graphs and Dijkstra’s algorithm to find the best route through a network.