Graph Theory: Basic to Advanced

The mathematics of relationships

Graph theory asks about structure rather than quantity: what is connected to what, and what follows from that. It is unusually practical for a subject this elegant, turning up in networks, scheduling, routing, dependency resolution and — through the spectral material at the end — in modern machine learning.

This course runs from vertices, edges and the handshake lemma to the graph Laplacian and spectral clustering.

Modelling is the hard part

Once a problem is correctly expressed as a graph, the right theorem is frequently obvious. The difficulty is almost entirely in getting there.

A problem about people shaking hands at a party is a degree problem. A problem about scheduling examinations so that no student has a clash is a colouring problem. A problem about whether a sequence of moves can reach a given position is a connectivity problem. None of them say so.

We work the modelling step explicitly rather than handing students a graph and asking them to apply a theorem — which is how the subject is usually taught and why students then cannot use it.

Degree arguments go a long way

The handshake lemma says the sum of all degrees is twice the number of edges, because every edge is counted at each end. It is immediate, and it does an astonishing amount of work.

It yields at once that the number of odd-degree vertices is even — which settles a whole genre of competition problem on its own. Students who reach for something sophisticated before checking what degrees tell them routinely waste an hour.

Two questions that sound alike

An Eulerian circuit uses every edge once; a Hamiltonian cycle visits every vertex once. The questions sound like siblings and are nothing of the sort.

Euler settled his completely: a connected graph has an Eulerian circuit exactly when every vertex has even degree. You check the degrees and you are done. No such characterisation exists for Hamiltonian cycles. The problem is NP-complete, and what we have are sufficient conditions — Dirac's, Ore's — rather than an answer.

This is the clearest illustration in elementary mathematics that surface similarity between two problems says nothing at all about their difficulty, and it is worth a student's attention for that reason alone.

Matching, colouring, planarity

Hall's marriage theorem gives the exact condition under which a complete matching exists in a bipartite graph, and it is one of those results that feels obvious once stated and is not at all obvious before. Augmenting paths make it constructive.

Colouring is the natural model for conflict and scheduling: chromatic number, greedy colouring, Brooks' theorem. Planarity brings Euler's formula relating vertices, edges and faces, and Kuratowski's characterisation of which graphs can be drawn without crossings.

Flows, and modelling in disguise

Network flow and the max-flow min-cut theorem are included partly for themselves and partly because flows are a modelling tool of unexpected range.

Problems with no apparent connection to networks — bipartite matching, certain scheduling and assignment problems, some partitioning questions — become flow problems under the right construction, and then a standard algorithm solves them. Recognising that is a genuine skill.

Where graphs become linear algebra

The final unit is the bridge to the research mathematics in the Advanced Maths for Research course.

The graph Laplacian is the degree matrix minus the adjacency matrix. It is positive semidefinite, its smallest eigenvalue is zero, and its second smallest — the algebraic connectivity or Fiedler value — measures how well connected the graph is. The Cheeger inequality ties that eigenvalue to how hard the graph is to cut in two.

That single eigenvalue underpins spectral clustering, and the Laplacian eigenvectors provide a Fourier transform on graphs, which is the mathematical foundation of graph convolutional networks. A student who understands this unit understands why graph neural networks are built the way they are.

Who this suits

Students from Class 9 upward through undergraduate study, with school algebra and some comfort with proof. No prior graph theory is assumed and no programming is required — algorithms are taught as mathematical procedures with their correctness argued.

Classes are live and online in groups of at most eight, with written work corrected individually.