Season 11 Episode 3

Jonathan is on OOMC to show us Pick's Theorem for the area of a polygon, and a proof for why it always works!

Watch on YouTube

Further Reading

Graph theory

Mid-way through Jonathan’s proof, we needed a fact about planar graphs. A graph is a collection of points (called vertices) and lines (called edges, and not necessarily straight lines) in the plane, with each edge connecting two vertices. A planar graph is one that can be drawn with no edges crossing.

The key challenge there is the word “can”. If you see a picture of a graph, then it can be tricky to decide whether it can be re-drawn so that no edges crossing.

There’s a relatively well-known puzzle that builds on this idea, and it’s called the utilities problem.

For more graph theory, you might like to have a look at the lecture notes for our second-year Graph Theory course. In the second year of the Oxford Mathematics degree, students choose five or six long options, and three short options. This is one of the short options, and it's designed to give people an impression of what third-year Graph Theory might be like. I've linked to it here because I don't think you need any first-year mathematics to understand what's going on (although it is mathematically sophisticated, so it's not an easy read!).

If you’d like a book about graph theory instead, the reading list for that course includes Introduction to graph theory by Robin Wilson, and Introduction to graph theory by Douglas Brent West.

Euler’s formula

A graph is called connected if you can get from any vertex to any other vertex along the edges. I’m not sure we said this in the livestream, but we’re definitely talking about connected graphs in this episode (for example, we’re not trying to find the area of a region made up of two separate shapes that aren’t connected).

We used a fact about connected planar graphs; counting \(V\) vertices, \(E\) edges, and \(F\) faces (regions of the plane bounded by edges and vertices, including the infinitely-large exterior face outside our graph), we always have \(V-E+F=2\). Or \(V-E+F=1\) if you don’t count the exterior face.

This can be proved by induction (that’s a proof technique that’s covered in A-level Maths / Further Maths). As you add in edges, they either connect to the existing graph (in which case the number of faces doesn’t change, but the number of vertices and edges each go up by 1), or they connect two existing vertices (in which case the number of faces and edges each go up by 1). Either way, the value of \(V-E+F\) doesn’t change, so for any planar graph the value is the same as it would be for a graph that’s just one vertex with no edges at all; \(V=1\) and \(E=1\) and \(F=1\). (It’s important that I start with one vertex rather than nothing at all, because I want to say that any new edge always connects to something that was already there).  

I think it’s cool that there’s such a simple formula that applies to all connected planar graphs. What’s even better though, is that there is also a version for surfaces in 3D. If you’ve ever built a 3D shape out of those plastic polygons, then your shape will obey this formula too. There is one extra term, to do with the number of “holes” in the shape. Not like a missing piece, but like a doughnut where the surface is unbroken, but loops around on itself. The formal term here is “genus” for the number of distinct loops or handles or holes. The formula, called the Poincaré formula, is \(V-E+F=2-2G\) where \(G\) is the genus.

Primitive lattice triangles have area one-half

There's a neat little proof of this fact summarised on Wikipedia as follows; take any primitive lattice triangle and tile the plane with it (it’s not immediately obvious that this is possible, but there's a diagram!). The way to do this is to first build a parallelogram out of two copies of your triangle, and then tile the plane with that parallelogram pretty much in the way that you would tile the plane with squares or rectangles, all aligned the same way as each other. Now step back and look at a large tiled area and think about how many triangles you’ve used. Since six triangles meet at any lattice point and triangles have three corners, you've used about twice as many triangles as there are lattice points in that large area. But there is one lattice point per unit area (if this isn’t clear, imagine tiling the plane with squares instead). So the triangles have area one-half.

Pick’s theorem on Wikipedia has some diagrams of 3D shapes, showing that there isn’t a nice simple formula. The Wikipedia page links to two research papers about a not-simple way to extend Pick’s theorem to higher dimensions, both of which are too advanced for me!