Earlier this year I was involved with the construction of the `Giant 4D Buckyball‘, as part of the University of Edinburgh’s Innovative Learning Week. The sculpture was actually of something rather more complicated – the Cantitruncated 600-cell – but buckyballs (in various representations) were a fundamental building block. So, what exactly are they?
Julia’s description gives a good overview of the geometric route to the buckyball (and onwards to the full sculpture). But one of the wonderful things about mathematics is that there are often multiple routes to the same place, with seemingly disparate sub-disciplines actually being the same idea in disguise. So my first exposure to the buckyball came not from thinking about physical geometry, but the rather more abstract world of graph theory. In this post I’ll describe the first step along this alternative route, planar graphs.
A graph is, in essence, a description of connections; a set of vertices wired together by edges. These can be used to understand literal networks, of course: phone systems, power grids, airline routes; less tangible connections such as the friendships in your `social network’; all the way through to purely abstract mathematical structures. My PhD research re-posed a problem in number theory in the context of some special types of graphs, with one of the main advantages being that drawing them gave a visual way to understand and reason about their structure.
But there are many, many ways to draw a particular graph, and generally no way to say that one of them is `right’. So thinking about a graph in terms of a drawing of it can be dangerous – you have to be certain that the arguments you’re making apply to all representations of the abstract graph, not just the one you’ve picked. Remarkably, it is possible to make such sweeping statements. This is illustrated by the concept of a planar graph. This is one which it is possible to draw in a 2D plane (e.g. on a piece of paper) without any of the lines joining up the vertices crossing over each other. It’s important to realise that just because a particular drawing has crossings, it doesn’t mean that there isn’t a better one without them. A single successful example of course does the trick for proving a graph is planar:
This example above shows two attempts at drawing a graph known as K4 – this has four vertices, and each one is connected to the other three by an edge. The first drawing might lead you to think it isn’t planar, but the second proves that it is.
From my travels: Graffiti at MIT, of a `proof’ that the K5 graph (five vertices, each joined to the other four) is not planar. Whilst a delicate argument can be made in this way, it’s a lot easier to identify rules for all planar graphs than it is to be sure you haven’t missed a case when reasoning geometrically.
If a graph is planar, then any drawing of it without crossings is known as an embedding. Any such drawing will divide the plane up into regions separated by the edges -we call these the faces, and include the infinite face which is the region on the `outside’ of the graph. For each of these faces, we define its degree to be the number of edges we’ll travel along if we were to walk all the way around its boundary.
A graph with 4 faces – the fourth, D, is the infinite face.
Usually the degree is obvious, but a little bit of care is required. In the example above, face A has degree 3, and face B has degree 4. But face C is not another triangle like A – we have to walk to the vertex in the middle and back, so it ends up with degree 5. Finally, the infinite face D has degree 6. However, if we pick a different embedding, we get a different list of degrees:
Another embedding of the same graph.
As a mathematical abstraction, this is the same graph as drawn before – all the connections between vertices are the same, we’ve just placed one of them at a different location in the plane. Since this hasn’t introduced any crossing edges, it’s a perfectly good embedding; but now face C has degree 3, and face D has degree 8. This means that the precise list of degrees can depend on the embedding – we say that it is not an invariant of the graph.
Identifying invariants is both a challenge and an opportunity: on the one hand, we have to be sure that something is true for any possible drawing of a graph for it to earn this status; but on the other, we will be able to control just how weird an embedding can get if we know it is forced to respect some invariant property.
A particularly useful tool for this is Euler’s Formula:
Let V be the number of vertices in our planar graph G, and E the number of edges; suppose as well that the graph is connected, which is to say that we can walk from any vertex to any other along some path made out of the edges. If there is an embedding of G with F faces, then
V – E + F = 2.
Since the number of vertices and edges never changes (and nor does the value of 2), this immediately tells us that the number of faces is an invariant: it’ll be 2+E-V.
Whilst the specific list of degrees of the faces can vary, it turns out that their sum is invariant; this is known as the handshaking lemma for planar graphs:
The sum of all face degrees of an embedding is twice the number of edges E in the graph.
These two simple results allow us to say a lot about possible planar graphs. For instance, you can combine them to show that if a graph is planar, then E≤ 3V-6 – effectively, if there are too many edges relative to the number of vertices, then you won’t be able to draw them all without a crossing (which makes intuitive sense). This makes life a lot easier for our graffiti artist above: in K5 we have V=5 so 3V-6 = 9, but there are 10 edges that we need to draw, so it’ll be impossible to do so in the plane without introducing a crossing.
If we do have an embedding then, since the simplest possible face is a triangle, any face has degree at least 3. So (by handshaking) we find that 2E≥ 3F.
So now we know a little bit about possibilities for some special graphs in the 2D plane. But how is that of use in understanding 3 dimensional objects? For that, we need the idea of projection, which is the topic of the next post.