1
Read and build the representations
Adjacency matrix, adjacency list and drawing — and know which makes a given question easy.
Course · Discrete Mathematics
Graphs and Trees
The discrete structure that models everything with a relation on it: networks, dependencies, maps, molecules, schedules. Every theorem in this course is a claim about all graphs, and the lab lets you try to break each one.
Σ deg(v) = 2|E| the handshake theorem
tree ⟺ connected and |E| = |V| − 1
Euler circuit ⟺ connected and every degree even
|V| − |E| + |F| = 2 Euler's formula, planar graphs
What this course is about
- Subject
- Discrete Mathematics
- Lessons
- 14
- Format
- Interactive
Overview
What you will be able to do
By the end you can model a problem as a graph, run the standard algorithms, recognise a tree and rule out planarity by counting, and know which questions have easy criteria and which do not.
2
Apply the standard criteria
Euler's degree condition, bipartiteness as the absence of odd cycles, and the tree characterisation, each with the proof behind it.
3
Run the algorithms
Breadth-first and depth-first search, Dijkstra, Kruskal and greedy colouring, and say what each guarantees.
4
Tell easy problems from hard ones
Euler circuits are decided in one pass; Hamilton circuits are NP-complete. The problems look alike and are not.
5
Recognise a tree, and rule out planarity by counting
Any two of connected, acyclic and n − 1 edges give the third; the three traversal orders from a drawing; and E ≤ 3V − 6 or E ≤ 2V − 4 settling non-planarity before any drawing is attempted.
Lessons
14 lessons
First the basics, then the structure of a graph, then traversals and paths, then trees, and last colouring and planarity.
Graphs and Graph ModelsVertices, edges, and the things they model.Not marked
Degree and the Handshake TheoremThe degrees sum to twice the edges — always.Not marked
Graph RepresentationsAdjacency matrix, adjacency list, and what each makes cheap.Not marked
Paths and ConnectivityWalks, paths, cycles, components — and what disconnects a graph.Not marked
Subgraphs and Graph IsomorphismWhen two different drawings are the same graph.Not marked
Bipartite GraphsTwo-colourable, and equivalently free of odd cycles.Not marked
Euler and Hamilton PathsEvery edge once, or every vertex once — and the two are nothing alike.Not marked
Breadth-First and Depth-First SearchTwo ways to visit everything, with different shapes and different uses.Not marked
Shortest Paths and Dijkstra's AlgorithmFewest edges is not cheapest route.Not marked
TreesConnected and acyclic — and five other equivalent descriptions.Not marked
Rooted Trees and TraversalsPreorder, inorder, postorder — three ways to visit every node.Not marked
Spanning Trees and Minimum Spanning TreesConnect everything with as few — or as cheap — edges as possible.Not marked
Graph ColouringColour the vertices so no edge joins two of the same colour.Not marked
Planar Graphs and Euler's FormulaDrawable without crossings, and the formula that constrains it.Not marked
Recommended background
Proof, sets, relations and counting.
Practice suggestions
Use the workbench adversarially. Every theorem here is a claim about all graphs, and the fastest way to understand one is two minutes spent trying to build a counterexample.
Draw the small cases. Graph theory is one of the few parts of mathematics where the picture is the object, and most of these proofs were found by drawing.
Where a lesson has a worked example that fits, its lab opens on it: the preset "This lesson's example" is that graph, with the lesson's own weights where it has them, and the panel quotes the figures you should see before you change anything. “Shortest Paths and Dijkstra's Algorithm” and “Spanning Trees and Minimum Spanning Trees” carry weights; “Paths and Connectivity” names the bridges, “Rooted Trees and Traversals” prints all four traversal orders, and “Planar Graphs and Euler's Formula” runs the planarity counts.
Notice which criteria are one-pass checks and which are searches. That distinction is what Algorithms and Complexity formalises, and it is visible here first.
What it does not cover
Directed graphs beyond passing mentions. Everything here is undirected unless stated; digraphs, strong connectivity and topological sorting are noted where they matter and not developed.
Network flow, matching algorithms beyond the bipartite criterion, and the algorithmic side of matching.
Spectral graph theory, random graphs and extremal graph theory, each of which is a course in itself.