On pi day this year, I gave a talk with the same title as this post at A Taste of Pi, an event organized by SFU to introduce high school students to math. I’ve decided to tell a story about the history of graph theory as a gentle introduction to the area.
Slides to my pi day talk: here
To make graph theory accessible to high school students, I made a lot of pdf images. I’ve decided to convert some sequences of my pdf animations into gifs. Here are my two favourites. It might be necessary to click on them, to get them to animate.
Cardioids:
One way to draw an eulerian planar graph is to simply draw closed curves on a piece of paper and add vertices where the curves intersect. The result is a plane drawing of an eulerian planar graphs … whose faces can be coloured with 2 colours.
But we need not draw any random doodle (although that is also fun), we can draw an approximation to a cardioid as follows:
- We start with a circle C with a defined point P.
- Draw a circle whose centre is at a point Q on C and pass through point P.
- Repeat step 2 until satisfied. (Repeat for all choices of Q to be a cardioid.)
2-face-colourability of eulerian planar graphs:
It is well-known that the faces of planar eulerian graphs are 2-colourable. If we take the planar dual Y of an eulerian plane graph X, we see each face of Y has even degree, since each vertex of X has even degree. Since the facial walks of a planar graph generates its cycle space, this implies that Y is bipartite.
Here is an illustration of the simpler, inductive proof:
