Season 5 Episode 7
Jonah is back on the livestream to introduce graph theory, including a proof that the utilities problem can't be solved on a plane.
Further Reading
Graph Words
Graph Theory is full of fun words. Here are some of my favourites;
Isomorphisms
If two graphs have the same number of vertices and edges, and same set of degrees for those vertices, are they isomorphic?
If yes, prove it! If no, what’s the "smallest" counterexample (with the fewest vertices)?
For "labelled trees" (graphs with no cycles, and where the vertices are numbered to distinguish them), something like this is good enough. See Prüfer sequence for more.
Seven-colour theorem
We saw on the livestream that the utilities graph isn’t planar in flat 2D space, but it is planar on the surface of a torus (doughnut). This shows that planar graphs can be more complicated on the surface of a torus, and we might expect to need more colors if we’re trying to color a map on a torus. The result is that we need seven colours. There is a really nice picture of a map that needs seven colors on Wikipedia here. Perhaps strangely, this was proved years before the four-colour theorem.
Euler’s Polyhedral Formula
Here are twenty-one proofs of Euler's Polyhedral Forumla V-E+F=2 on a sphere. Some of them are much much more complicated than others, well beyond the scope of this maths club!
Slides
Jonah's slides are attached here.
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