A Fun Math Problem

The complete graph on four vertices has six edges and looks like this.

The black dots are called vertices, and the gray lines are called edges.

Now let’s say this is a game board, and I have one red token, which I will place on one of the vertices. First question: how many choices do I have? Well, there are four possibilities, so I have four choices. Here are my four possible choices:

We can now ask the following question. How many unique graphs are there? If you look at the four graphs above, you should be able to convince yourself that each is the same graph, just rotated 90 degrees each time. To get a mental model for this, imagine the leftmost graph was a real physical thing made out of tinker toys, and you picked it up and rotated it by 90 degrees. It’s still the same thing; it’s just rotated! So there is only one unique graph in the above four.

Let’s make this a bit more complicated. Let’s say I have two tokens, one blue and one red, and I need to place these on two different vertices. The total number of possibilities is now (4 choose 2) x 2 = 6 x 2 = 12 (the x 2 is because for each choice of 2 out of 4, we can swap the colors). Here are the 12 possibilities for how I can place my two tokens.

Again I can ask the question, how many unique graphs are there? It’s a little harder to see here, but the answer is still one. Here’s a way to visualize this.

Imagine for each of the above graphs, we rotate it either clockwise or counterclockwise until the red vertex is in the top right hand corner. Rotations don’t change any of the graphs so that’s fine to do.

Once we’ve done that, we do a little visualization trick. We imagine each of the graphs lives in three dimensions, and we ‘pull up’ the top right / red vertex to become the top node of a tetrahedron/pyramid (like a D&D D4, the bane of feet everywhere). Each pyramid has one red vertex on top, and one blue vertex and two black vertices on the base. Each of these is connected by a rotation around the pyramid’s base. So all of these graphs are the same graph.

We can define a canonical representation of this graph — one representation that we will use no matter which of these we get. I’ll call the version where the top right vertex is red and the bottom right vertex is blue the canonical representation for this graph. So we can write any of the 12 graphs above like this.

So far this has been pretty straightforward, but now let’s make it more interesting. In addition to placing the red and blue tokens, I also want to color each of the edges one of three colors — say black, green, or purple. So each edge has to have one of those three colors. This gives a total of 3⁶=729 possible edge colorings (each edge gives 3 different possibilities, and there are 6 edges, so the total number of colorings is just 3 multiplied by itself 6 times).

Here’s an example where I color two of the edges black, two green, and two purple. This isn’t meant to be special, just one of the 729 possibilities.

We place our red and blue tokens on this graph, and we get the following 12 different graphs, just like before, except now with edge colorings.

The question I want to answer is the following. In the set of all possible graphs with one red vertex, one blue vertex, and each edge colored with one of three colors, how many unique graphs are there?

We know an upper bound: each of the 729 colorings has 12 different token placements, so there are at most 12x729 = 8,748 unique states.

We also know that the number has to be smaller than this because we know from the first example that placing the tokens in different positions on a graph doesn’t have to generate new unique states. And also it seems clear that at least for some different edge colorings, placing the red and blue tokens in the right places will lead to the same end state.

Vertex Permutation Symmetries, AKA Automorphisms

To make progress here, let me introduce the concept of a vertex permutation symmetry, also known as an automorphism. In a graph, an automorphism is a mapping from one vertex labeling to another that preserves the edge structure of a graph. By running through the application of all automorphisms, we can enumerate all possible graphs that are ‘the same graph’.

For the complete graph on four vertices, there are 24 automorphisms. To see why, imagine I label the four vertices A, B, C, and D starting from the bottom left vertex and going clockwise around the graph. Now let’s say I move the A vertex to any possible position (there are 4), move B to one of the three remaining, C to one of the two remaining, and D gets the last spot, while being careful to maintain the original edge colorings (i.e. the edge A-B is the same color regardless of where I put A and B, etc.). There are 4x3x2 = 24 ways to do this.

Solving The Problem: Step 1

The first thing to realize is that each of the 8,748 possible graphs must have at least one equivalent graph that is in our canonical form (red vertex top right, blue vertex bottom right — for example in the image above, the top right graph is in canonical form). That’s because we can always find an automorphism that maps wherever they start out to these positions, because any two vertices can always be exchanged as long as we preserve the edge structure.

This means that all of the 8,748 graphs have at least one representation of this sort, which means there can be a maximum of 729 unique graphs (all edge colorings with red vertex top right, blue vertex bottom right).

So now the question becomes a bit simpler — for the complete graph on four vertices, where both leftmost vertices are colored black, the top right vertex is colored red, and the bottom right vertex is colored blue, where each edge can take on any of three values (black, green, purple), how many unique states are there?

Solving The Problem: Step 2

Because of the vertex coloring constraint, the remaining problem type now has only two symmetries. The first is the identity symmetry where we do nothing, and the second is the equivalency under swapping the labels on the black vertices.

To figure out how many unique states there are, accounting for these two symmetries, we can use Burnside’s lemma. Burnside’s lemma is a method for counting distinct objects under a group of symmetries — exactly what we need!

(By the way, sometimes I wonder if it’s worth me going down these dusty side roads to work through a problem carefully. I mean, it doesn’t really matter how many unique states of this graph there are to continue advancing on my ultimate goal of trying to show quantum computers can be made useful. But this is an example of why I still tend to do this. I had never even heard of Burnside’s lemma before I started working through this, but it is a super general, useful, and very non-intuitive (at least to me) result. I’m glad I learned about it!)

Here’s what the lemma says. If you want to count the number of distinct objects under a given set of symmetries, you just need to find out how many of the objects are fixed under each symmetry, add up these numbers, and divide by the number of symmetries. Like seriously, WTF?

Anyway. So here the number of symmetries is two ((1) Identity / do nothing, and (2) swap the black vertices).

The number of states fixed under the Identity group is … all of them (729). So all we have to do is figure out how many states are fixed under swapping the two black vertices and we are done.

This is pretty easy! The vertical edges (0-1) and (2-3) are unchanged under the swap no matter what they are, so that gives us two factors of 3. The middle edges have to be such that edge (0-2) is the same as edge (1-2) (this happens 3 times) and edge (0-3) is the same as (1-3) (this also happens 3 times).

So the total number of graphs that are unchanged under swapping the black vertices is 3x3x3x3 = 81.

Burnside’s lemma applied to this problem. Here |G| is the number of symmetries, Fix is the number of objects that remain the same under the symmetry, I is the identity symmetry, and swap is the symmetry under swapping the two black vertices.

This gives us the answer to the puzzle.

In the set of all possible graphs with one red vertex, one blue vertex, and each edge colored with one of three colors, there are 405 unique graphs.

This is also the number I get when I do everything computationally.

By the way, the reason I ended up looking at the result carefully is that I thought the computational result I was getting was wrong. I couldn’t figure out why there should be a factor of 5 in the answer, as the number of vertices and edges were both even, and the edge colorings were factors of 3. The intuition that an answer is wrong is a powerful tool for debugging. But in this case it appears my intuition that this was wrong was …. wrong!