OpenAha
00
All courses
Math · Intermediate

Graph Theory

A "graph" here means dots joined by lines. From Euler's bridges of Königsberg to GPS routing, map colouring, cheapest networks, the travelling salesperson, untangling puzzles and Euler's formula, discover how this simple idea models friendships, road networks, the internet and more, and why we live in a small world.

8 lessons~45 min0/8 complete
1

Paths

Euler and the bridges.

  1. The Seven BridgesWhere graph theory began
  2. The Handshake LemmaCounting degrees
2

Routes, Colours and Trees

Graphs at work.

  1. Shortest PathsHow maps find routes
  2. ColouringMaps and schedules
  3. TreesConnected, with no loops
3

Tours, Planes and Networks

Hamilton, Euler’s formula and small worlds.

  1. Hamiltonian ToursVisit every point once
  2. Planar GraphsDrawing without crossings
  3. Small WorldsSix degrees of separation

Courses that build on this

Ready for more? These courses use what you learn in Graph Theory.

Math · Advanced

Topology

Rubber-sheet geometry: holes, twists, knots, hairy balls and fixed points.

7 lessons3 chapters