Graph Theory
Discrete and Data
Networks from the ground up: degrees and isomorphism, connectivity, trees and spanning trees, shortest paths and minimum spanning trees, Euler and Hamilton tours, matchings, planarity, coloring, network flows, and Ramsey theory.
Start here
Graphs and Degrees
Unit 1 · Graphs and Degrees
0 of 11 units complete
- 1Unit 1Graphs and Degrees5 parts · about 12 min
Graphs and Degrees
Dots and lines: friendships, flights, molecules and the internet are all graphs. Draw them, count degrees, prove the handshake lemma, decide which degree lists are possible, and store a graph as a matrix.
- 2Unit 2Isomorphism and Subgraphs5 parts · about 11 min
Same Graph, Different Drawing
Two drawings can be the same graph in disguise. Take subgraphs and complements, decide when graphs are isomorphic using invariants, find a graph that is its own complement, and count how many graphs there really are.
- 3Unit 3Walks, Paths and Connectivity5 parts · about 12 min
Walks, Paths and Connectivity
Move around a graph: walks may repeat anything, trails never reuse an edge, paths never revisit a vertex. Count walks with matrix powers, find the bridges whose loss splits a network, and measure how robust a network is.
- 4Unit 4Trees5 parts · about 10 min
Trees
Connected, with no cycles: the simplest graphs, and everywhere from family trees to file systems. Count their edges and leaves, pick spanning trees out of bigger graphs, and meet Cayley's formula n^(n−2) and the codes that prove it.
- 5Unit 5Graph Algorithms5 parts · about 11 min
Graph Algorithms
How sat-navs find the fastest route and how networks get built for the least cost. Explore graphs breadth-first and depth-first, run Dijkstra's shortest paths by hand, build minimum spanning trees greedily, and put tasks in a safe order.
- 6Unit 6Eulerian and Hamiltonian Graphs5 parts · about 10 min
Euler and Hamilton
Can you draw the house without lifting your pen? Euler settled that in 1736 with the bridges of Königsberg and a single counting argument. Visiting every vertex instead turns out to be one of the hardest problems in computer science.
- 7Unit 7Bipartite Graphs and Matchings5 parts · about 10 min
Matchings
Pair people with jobs, students with schools, donors with patients. Spot bipartite graphs by their missing odd cycles, build the biggest matching, learn Hall's marriage condition, and see the Nobel-winning stable-matching algorithm.
- 8Unit 8Planar Graphs5 parts · about 10 min
Planar Graphs
Which graphs can be drawn with no crossing edges? Untangle drawings by dragging, discover Euler's V − E + F = 2, prove that three houses cannot all be connected to three utilities, and find the five Platonic solids hiding in a formula.
- 9Unit 9Graph Coloring5 parts · about 10 min
Graph Colouring
Colour the vertices so neighbours always differ, using as few colours as possible. Schedule exams without clashes, find why odd cycles and wheels need more colours, count colourings with a polynomial, and meet the four colour theorem.
- 10Unit 10Directed Graphs and Network Flows5 parts · about 10 min
Directed Graphs and Flows
One-way streets, food chains and pipelines. Learn when you can get from anywhere to anywhere, find who wins a round-robin tournament, and push as much flow as possible through a network until a bottleneck cut stops you.
- 11Unit 11Extremal Graph Theory and Ramsey Theory5 parts · about 10 min
Extremal Graphs and Ramsey Theory
How many edges can a graph have before a triangle is forced? And among six people, why must three be mutual friends or mutual strangers? Total disorder is impossible: some pattern always appears.