Season 12 Episode 2

You might have heard of the Four Colour Theorem, which tells you how many colours you need for a map. That's much too hard for an hour of OOMC, so instead we're aiming for the less ambitious Six Colour Theorem in this episode!

Watch on YouTube

Those lecture notes contain a proof of the five-colour theorem using induction on the size of the graph (page 21). The key idea is to consider a vertex with five or more neighbours that you haven't coloured yet. If the neighbours only use four colours, you can pick the remaining colour for this vertex and you're done. Otherwise, investigate whether you can flip the colour of one of the neighbours of a vertex (so that you have a colour free to colour this last vertex), or whether that flip would induce a chain of consequences that comes back to bite you by flipping the colour of another neighbour of your uncoloured vertex. The proof is that there's always such a chain, for planar maps. Those paths of vertices of alternating colours are called Kempe chains. A biography of Kempe including his work on the four colour map theorem can be found here.

Kempe believed that he had proved the four-colour theorem, publishing a proof in 1879. His proof had a subtle mistake that wasn't spotted until Percy Heawood identified it in 1890. Heawood showed that Kempe's argument, while not sufficient to prove the four-colour theorem, could be salvaged to prove the five-colour theorem instead, and that’s the proof that appears in the Oxford lecture notes above. The four-colour theorem was unsolved for another 80 years.

Philosophy and semantics

I mentioned in passing the difference between a number and a numeral. I was not quite correct in my distinction, so this is a sort of correction. A numeral is a symbol or word used to represent a number, so "3", "three", and perhaps even "..." are all numerals. A number is the abstract thing those symbols refer to; I can’t draw it on the board at all. It’s like the distinction between the word "envelope" which contains eight letters, and the concept of an envelope, which contains only one. There’s a Wikipedia article on numerals.

Lily mentioned the philosophical question "what are numbers?". Students on the Oxford Mathematics and Philosophy course read about one influential answer in Frege’s 1884 book The Foundations of Arithmetic. Frege argued that numbers are not physical objects, not mental ideas, but abstract logical objects; specifically, that the number $n$ is the collection of all concepts that have exactly $n$ things falling under them. This book is where the question "is Julius Caesar a number?" comes from. This question is still used as an essay topic in the Oxford Mathematics & Philosophy degree! You can read (a lot!) more about the philosophy of mathematics on the Stanford Encyclopedia of Philosophy article on the philosophy of mathematics.

Sleeping Beauty problem

Lily mentioned this conditional probability paradox: Sleeping Beauty problem. Unlike similar-sounding probability problems like the Monty Hall Problem, for this one there's no consensus on what the answer is supposed to be!

Euler's formula

It's such a good formula! For any connected planar graph with $V$ vertices, $E$ edges, and $F$ faces (counting the outer, unbounded face), we have $V - E + F = 2$. In that statement, I’ve used the word "connected", which just means that you can get from any vertex to any other vertex along the edges (in general, graphs are allowed to have several separate connected components that don’t connect to each other. In a map-colouring context, that would be like having countries on separate continents that don’t connect. For Euler’s formula, we’re talking about a connected graph)

Here is a proof sketch by induction.

Proof. Induction on the number of edges $E$.

Base case. If $E = 0$, the graph is a single vertex (since it's connected), so $V = 1$ and $F = 1$ (just the infinite outer face). Then $1 - 0 + 1 = 2$. All good so far!

Inductive step. Suppose the formula holds for all connected planar graphs with fewer than $E$ edges, and let $G$ be a connected planar graph with $E \geq 1$ edges. There are two cases:

If $G$ has no cycles, then $F = 1$ (there are no enclosed regions, just the outer face) and $V = E + 1$ (the graph can be constructed one vertex at a time, adding new edges one at a time). So $V - E + F = (E+1) - E + 1 = 2$.

If $G$ contains a cycle, then there is some edge $e$ that lies on the boundary between two distinct faces. Remove $e$: the resulting graph is still connected (since $e$ was on a cycle, there's another path between its endpoints), has $V$ vertices, $E - 1$ edges, and $F - 1$ faces (the two faces that were separated by $e$ have merged into one). By the inductive hypothesis, $V - (E-1) + (F-1) = 2$, which gives $V - E + F = 2$.

By induction, the formula holds for all connected planar graphs. $\square$

Note that this is a sketch. In particular, I’ve glossed over the details of what it means to construct a graph "one vertex at a time" in the first bullet point, and in the second bullet point the claim "removing a cycle edge merges exactly two faces into one" needs more work to prove properly.

Mathematics has got quite a lot of this sort of thing, where you need intuition to understand what’s going on, but you also need a rigourous proof to understand exactly what’s going on. For example, the Jordan curve theorem (relevant to the details I’m skipping above) https://en.wikipedia.org/wiki/Jordan_curve_theorem broadly just says that every closed loop in the plane has an inside and an outside. Maybe that doesn’t sound like it needs a proof, but for a mathematician it definitely does!

Another example is my claim on the OOMC episode that "any face of a planar graph has at least three edges". In the livestream I think I even glossed over the fact that this is patently untrue for small graphs. An actual proof has to be really careful because, even for a planar graph, the object that we're really working with is an abstract set of vertices and a list of edges, together with (because it's planar) some way to embed that in the plane ("draw it on a whiteboard with no edges crossing"). Any concepts that we would like to use such as "walk around the cycle in a clockwise direction" need to be developed from scratch!

Planar graphs

In this episode I challenged you to decide whether the graphs $K_4$ (four vertices, all possible edges) and $K_{3,3}$ (three vertices on the left, three vertices on the right, every possible edge from left to right, no other edges) are planar. Here are some more to consider:

$K_5$, the complete graph on five vertices.
$K_{2,3}$, the complete bipartite graph with two vertices on one side and three on the other.

The graphs $K_n$ are called complete graphs. The graphs $K_{a,b}$ are called complete bipartite graphs.

Yes, I know "complete" doesn't start with K! Some people say the letter K is used in honour of Kazimierz Kuratowski. Kuratowski's theorem, one of the great results in graph theory, says that a graph is planar if and only if it contains no subdivision that matches one of two particular graphs (two of the graphs above!). Those two graphs are in a precise sense the only "reasons" a graph can fail to be planar.

The graph $K_{3,3}$ appears in the famous utilities problem: NRICH: Connecting Utilities.

If you want to get in touch with us about any of the mathematics in the video or the further reading, feel free to email us on oomc [at] maths.ox.ac.uk.

Season 12 Episode 2

Further Reading

Graph theory

Philosophy and semantics

Sleeping Beauty problem

Euler's formula

Planar graphs