Season 5 Episode 7

OOMC Season 5 Episode 7. Graphs with Jonah

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

Last updated on 27 Feb 2023, 4:40pm. Please contact us with feedback and comments about this page.