Graph Theory Course Guide: Basic to Advanced
Once a problem is correctly expressed as a graph the right theorem is often obvious. The difficulty is almost entirely in getting there.
A graph theory course teaches a subject that is unusually practical for how elegant it is. Graphs ask about structure rather than quantity — what is connected to what, and what follows from that — and the answer turns up in networks, scheduling, routing and modern machine learning.
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 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.
A good graph theory course works 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 the degrees tell them routinely waste an hour.
Trees, and why they are the easy case
Trees and their equivalent characterisations, leaves, rooted trees, spanning trees, Cayley's formula, and minimum spanning trees with Kruskal and Prim.
Trees matter disproportionately because so many harder results are proved by reducing to a tree, and because the algorithms are the first place a student sees a greedy method that is provably optimal. That proof — that taking the locally best edge really does produce the globally best tree — is worth dwelling on, since greedy methods usually do not work and students should know why this one does.
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. 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 about their difficulty, and it is worth a student's attention for that alone.
Matching, colouring, planarity
Hall's marriage theorem gives the exact condition under which a complete matching exists in a bipartite graph. It is one of those results that feels obvious once stated and is not at all obvious before, and augmenting paths make it constructive.
Colouring is the natural model for conflict and scheduling: chromatic number, greedy colouring, Brooks' theorem, edge colouring.
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 and one of the more satisfying moments in the course.
Extremal and Ramsey arguments
Turan's theorem, the extremal number, Ramsey numbers and their small values, and the probabilistic method applied to graph existence results.
These overlap heavily with our combinatorics course, which is unsurprising: graph theory is in large part combinatorics on a particular structure. Students doing both find the techniques reinforce each other.
Where graphs become linear algebra
The final unit is the bridge to research mathematics.
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.
The linear algebra it assumes comes from our algebra course, and it leads directly into the spectral material in Advanced Maths for Research.
Where to start if the subject is new
Graph theory has an unusually gentle entry point, which is worth knowing because the later material looks forbidding.
The first weeks need nothing beyond careful reasoning: draw the graph, count the degrees, check connectivity. A student with no background can make real progress immediately, which is not true of calculus or abstract algebra.
The difficulty curve then rises steadily rather than abruptly, and the only genuine prerequisite that appears later is the linear algebra needed for the spectral unit. A student who plans to reach that material should have matrices and eigenvalues secure before starting it, and can build them in parallel.
Who this suits
Students from Class 9 upward through undergraduate study, with school algebra and some comfort with proof.
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.
It is the course with the clearest line to applied work: a student who finishes it can read about network algorithms, recommendation systems or graph neural networks without the mathematics being the obstacle.
Questions people ask
What makes graph theory useful beyond competitions?
It is the mathematics of relationships, so it appears wherever structure matters: networks, scheduling, routing, dependency resolution, recommendation systems and modern machine learning through graph neural networks.
What is actually hard about it?
Modelling. Once a problem is correctly expressed as a graph, the right theorem is often obvious; the difficulty is seeing that a problem about people shaking hands, or scheduling without conflicts, or a sequence of moves, is a graph problem at all.
Why is Hamiltonian so much harder than Eulerian?
Euler gave a clean necessary and sufficient degree condition for an Eulerian circuit, so the question is settled by inspecting degrees. No comparable characterisation exists for Hamiltonian cycles; the problem is NP-complete and the known results are sufficient conditions rather than a full answer.
Do I need programming?
No. Algorithms such as Kruskal, Prim and Ford-Fulkerson are taught as mathematical procedures with their correctness argued rather than their code written. Students who do program find the implementations straightforward afterwards.
What is the graph Laplacian for?
It is where graph theory becomes linear algebra. Its second smallest eigenvalue measures how well connected the graph is, which underpins spectral clustering, and its eigenvectors give a Fourier transform on graphs, which is the foundation of graph convolutional networks.
Get a study plan for this
Tell us the class and what they are working towards, and we will send a plan built around it, plus the next free trial class. No cost, and we will not pass your details on.
