Advanced undergraduateDiscrete MathematicsPlanned

Graph theory

Connectivity, matchings and Hall's theorem, colouring, planarity and Euler's formula, extremal results such as Turán's theorem, and Ramsey theory.

math.discrete.graph-theory

The lesson for this topic has not been written yet. The outline below is part of the curriculum map and has not been reviewed.

Builds on

Required prerequisites, all the way down: 18

Prove Hall's marriage theorem and apply it.
Prove Euler's formula V − E + F = 2 for connected plane graphs and deduce that K₅ and K₃,₃ are not planar.
Prove that R(3, 3) = 6 and establish upper bounds for Ramsey numbers.

A matching is a set of edges no two of which share a vertex.
A proper k-colouring assigns one of k colours to each vertex so that adjacent vertices receive different colours.
The Ramsey number R(s, t) is the least n such that every red–blue colouring of the edges of Kₙ contains a red K_s or a blue K_t.

Hall: a bipartite graph with parts A and B has a matching covering A if and only if |N(S)| ≥ |S| for every S ⊆ A.
Four colour theorem (Appel and Haken, 1976): every planar graph is 4-colourable; the proof relies on computer verification.
Kuratowski: a graph is planar if and only if it contains no subdivision of K₅ or K₃,₃.
R(3, 3) = 6.

Thinking a graph is planar only if a given drawing has no crossings; it is planar if some drawing has none.
Assuming the four colour theorem has a short proof checkable by hand; known proofs use computers, and one has been formally verified in Coq.

Computational complexity Deciding whether a graph is 3-colourable is NP-complete.
← Algorithm design and analysis