Things About NAP Scores

I've been thinking a lot about asymmetric graphs this summer. After making my game NAP, I've been thinking about the best way to make asymmetric graphs. The game works like this: You're given some symmetric graph and you need to add vertices and edges economically in order to make the graph asymmetric (i.e. make the graph have no nontrivial automorphisms). I say economically because the goal is to minimize your score, where a new edge gives you 1 point and a new vertex gives you 2 points. It's a fun daily puzzle and good exercise for those geometric brain cells. But naturally, I can get a bit competitive with it. It's already tricky sometimes to get a reasonably low score for many of the puzzles, but I want the best score.

bean playing NAP

It's really fun when digging around new concepts to make cool-sounding words to use. In this case, because there is so little online about asymmetric graphs, I feel like I can make up some terms (for fun, at least). The nonexistent words asymmetrize and desymmetrate get the idea across, which is probably what I should be striving for, but are really lame. Busting out a list of Latin/Greek roots, I've decided on anisocrate, which will be our cool-sounding word for the act of making a symmetric graph asymmetric. (I also made up and like aggrechirate and anihichirate for anisocrations that involve only adding nodes/edges and only subtracting nodes/edges, respectively.) Thus, the goal of NAP is to give the cheapest anisocration of the starting graph.

Since each starting graph is different, there's no way to easily define the best score arbitrarily. Instead, we might ask a better question:

Can we define a function that, given a number of vertices n, returns the worst possible score a perfect player can get with a starting graph that has n vertices?

In other words, we want a function W(n) such that if we start with a graph that has n vertices and we score greater than W(n), we are certain we can do better.

Before we start, it'll be helpful to find the smallest asymmetric graph. To do so, we'll start with the following theorem.

Theorem 1. A graph G is symmetric if and only if its compliment G' is symmetric.
compliments of symmetric graphs are symmetric
The top graphs are symmetric and the bottom graphs are both asymmetric, examples of Theorem 1.

Proof. If \(G\) is symmetric, then there exists some nontrivial automorphism \(A\) of \(G\). We want to show that \(A\) is also an automorphism of \(G'\). Let \(V\) be the set of vertices of \(G\). We have for all vertices \(v\) of \(V\), there is some vertex \(w\) such that \(A(v) = w\). If \(N_x\) is the set of neighbors of a vertex \(x\) (the set of all vertices connected via one edge to x), then, by definition, \(A(N_x) = N_x\). Now let \(v'\) be the corresponding vertex to \(v\) of \(G'\). Then, because \(G'\) is the compliment graph of \(G\), \(N_{v'} = V - N_v\). So we have that \begin{align} A(N_{v'}) &= A(V - N_{v})\\ &= A(V) - A(N_v) \\ &= V - N_v\\ &= N_{v'}.\end{align} Thus \(A\) is an automorphism of \(G'\). \(\Box\)

Now we can start looking at graphs with a small number of vertices n. When n = 1 or n = 2, it's easy to see there are no asymmetric graphs (ignoring, for convenience, that the graph of 1 vertex is technically asymmetric; we'll see why it's nice to call this symmetric later). When n = 3, there are only four graphs we need to check:

all graphs we need to check with three nodes
These are all clearly symmetric, so we can move on to n = 4. This is a bit tougher, because the number of graphs of n vertices rises quickly as n increases. But here we can be a little tricky (or lazy!), and use Theorem 1 to say that we actually only need to check graphs with 4 vertices and \(\frac{1}{2}\cdot\begin{pmatrix}4\\2\end{pmatrix} = 3\) edges, since if a graph had more than three edges, we would have already considered its compliment, which must have three or less. Furthermore, we only have to check such graphs that are connected, since if we found a disconnected asymmetric graph of four vertices, we would need an asymmetric graph of less than four vertices. Using these tricks, we're able to shrink our considerations down to only two graphs, both of which are clearly symmetric:
the two graphs we need to check with four nodes

Similarly for graphs of five vertices, we can look at those graphs which are connected and have \(\frac{1}{2}\cdot\begin{pmatrix}5\\2\end{pmatrix} = 5\) edges or less. This ends giving us eight different graphs, which are all also symmetric.

Finally, for graphs of six vertices, we can use the same techniques to find four graphs that are connected and have \(\lfloor\frac{1}{2}\cdot\begin{pmatrix}6\\2\end{pmatrix}\rfloor = 7\) edges that have no automorphisms. So, with their compliments, we reach the eight asymmetric graphs with six vertices:

six-node asymmetric graphs

We can see that the graph in blue is the cheapest asymmetric graph, as in it has the fewest nodes and edges. So, when we are solving for W(n) for n < 6, we might consider working towards this cheapest asymmetric graph. Because of this, we will call this graph the cheap ass. graph (for cheap asymmetric graph), or C for short.

To start, when n = 1, we only have one choice for the graph. We need five vertices and 6 edges to get to C, so both the best and worst score for starting with a graph of one vertex is W(1) = 5*2 + 6 = 16. For n = 2, we would be lucky to start with two vertices connected by an edge, but we must consider the worse case of two vertices not connected by an edge; in this case, we would need four vertices and six edges, for a total of W(2) = 4*2 + 6 = 14. Similarly, for three nodes we would start with three unconnected vertices, so we'd need three vertices and six edges to get to C, meaning W(3) = 3*2 + 6 = 12.

best scores for low values of n

To recap, we have

W(0) = 18
W(1) = 16
W(2) = 14
W(3) = 12

With n = 4, things get more interesting. We can notice that if we start with four unconnected vertices, we'll need only two vertices and six edges to get to C, giving us W(4) = 10. But, since our goal is to find the worst possible starting graph with four vertices, we can perhaps look for a graph that isn't a subgraph of the eight six-vertex asymmetric graphs above. The only such graph with four vertices is the complete graph K₄. Here's where things get tricky: starting with K₄, what's the best possible score?

Because K₄ is not a subgraph of any of the asymmetric graphs above, we know we must have at least seven vertices, so let's go ahead and add the three more we need. Now our goal is to connect these three vertices to the K₄ with the fewest amount of edges. Well, we clearly can't use fewer than three edges, since if we could, we might as well not use one of the added vertices. We'll first notice something critical:

Remark 1. When starting with a complete graph, we need to 'interact uniquely' with every starting vertex except for one. Otherwise if we have more than one vertex not interacted with uniquely, we can define some automorphism that permutes those vertices.

Here, 'interacting uniquely' means that we need to add an edge to each starting vertex, connecting it with some unique subgraph. For example, we can try adding the three nodes to our K₄ without interacting with all but one starting vertices:
trying to solve k4 but not interacting with all nodes
But this configuration allows us to swap those uninteracted vertices. We can try to interact with all but one starting vertices, but do so non-uniquely:
interacting with the nodes non-uniquely
This, of course, doesn't work either.

Here, we can see we at least need to add a fourth edge. Doing so allows us to make this configuration:

compliments of symmetric graphs are symmetric
Asymmetric! We added three vertices and four edges, so we have a score of W(4) = 10. This happens to be the same score as starting with four unconnected vertices. We'll see that things only get more complicated.

Before we go to five vertices, we naturally notice a pattern. Starting with zero vertices and going up, we have scores of 18, 16, 14, 12, and 10 for n from 0 to 4. It becomes really tempting to say W(n) = 18 - 2n. Let's see how long we can maintain this model...

For a starting graph of five vertices, we first have to ask what the worst possible starting graph is. Starting with 5 unconnected vertices is actually kind of nice, since we're only one vertex and six edges from C, so a score of 8. So we'll consider the other extreme: the complete graph K₅. Should we consider K₅ minus any edges, since this might be as hard as solving K₅ but in the end will need one extra edge? Well, at least in this case, it seems like no; removing an edge would make it closer to solving the K₄. So, let's find the best score for K₅.


It's actually pretty hard to find the best score, so let's first find a way to anisocrate it with a decent score. One way to do this is with what I call the Tall Hat Method. I picture in my head a party of wizards standing around a magical pentagramal carving in the floor, preparing some kind of ritualistic spell or something. These wizards are pretty petty, though, and like to outclass each other by wearing a taller hat than their neighbor. It looks like this:

Tall Hat Method of solving a complete graph

It's clear that no hat is isomorphic to any other hat, which means that the original vertices can no longer permute, and we made sure to not add any symmetry. Without a solid proof, we'll claim that this method of adding vertices and edges does break all symmetries. This means that for any complete graph (with four or more vertices), we can anisocrate it with tall hats. We can do this on K₄ and notice that, needing only two hats, we have three added vertices and five added edges, making a score of 11. Not optimal, but not bad either. On our K₅, we only need three hats, so that makes six added vertices and nine added edges for a score of 21. Indeed, we can continue this pattern for any complete graph of n vertices, noticing that the kth hat has a score of 3n + 1 and doing some algebra to derive a formula:

Work We notice that the \(h\)th hat gives a score of \(3h + 1\). Using the finite summation formula, we get \begin{align} \frac{h(4 + 3h + 1)}{2} = \frac{3h^2 + 5h}{2} \end{align} total points after \(h\) hats. Notice, though, that \(K_n\) only needs \(n-2\) hats, so we can plug in \(h = n-2\) to get \begin{align} \frac{3(n-2)^2 + 5(n-2)}{2} &= \frac{3(n^2 - 4n + 4) + 5n - 10}{2}\\ &= \frac{3n^2 - 12n + 12 + 5n - 10}{2}\\ &= \frac{3n^2 - 7n + 2}{2}. \end{align}

So, for any complete graph of n vertices, we can say that we can at least get a score of \(\frac{3n^2 - 7n + 2}{2}\).

What I'm about to do is kind of ill-mannered, devious, and vile. I want to make an assumption, without proof, about graphs, so that working with our W(n) function is a bit easier. It's a pretty believable assumption to me, but I'll make it clear when I use it and what the alternative would be if it were false.

Conjecture 1. For n > 4, the complete graph of n vertices is the worst possible starting graph of all graphs with n vertices.

Assuming this, we can immediately start to bound W(n).
Theorem 2. For \(n\) starting vertices, the worst possible score a perfect player can make is \(W(n) \leq \frac{3n^2 - 7n + 2}{2}\).

But I think we can do better. Perhaps we can stick with the hat idea, but consider whether or not we always need to add an extra vertex to make a new hat. That is, can we make nonisomorphic hats with the same number of vertices? Yes! I call this the Antler Hat Method, imagining that during the holiday season, the wizards festively meet for their magic circle after turning their hats into reindeer antlers. We can partition the nodes on a hat into two antlers in \(\lceil\frac{n}{2}\rceil\) distinct ways.

The Antler Hat Method
This means we get a pattern that looks like
Hats h Vertices of hth Hat Edges of hth Hat Score of hth Hat Total Score
1 1 2 4 4
2 2 3 7 11
3 3 4 10 21
4 4 5 13 34
5 4 5 13 47
6 5 6 16 63
7 5 6 16 79
8 6 7 19 98
9 6 7 19 117
10 6 7 19 136
11 7 8 22 158
... ... ... ... ...

Things don't actually improve until K₇; the Tall Hat Method gives us a score of 50 whereas the Antler Hat Method gives us a score of 47. A difference of 3 isn't great but it's not negligible. Because this new method, in a sense, recycles hats more and more as n increases, the Antler Hat Method far outpaces the Tall Hat Method for, say, n = 1,000,000,000.

Yet, we can probably still do better. The Antler Hat Method only uses two antlers, but if we used more antlers, we can keep conserving resources, at least when possible. We might call this the Partition Hat Method, because it depends on the number of partitions of the number of nodes. For that matter, we don't even need to just use antlers, we can connect our antlers in unique ways to save on resources. We might call this the Party Hat Method, because we're looking for unique asymmetric hats that have no certain form. And who says we need a new hat for each wizard? Perhaps if we arrange the hats in a certain way, we can reuse old ones. But wait, does each wizard need a hat, or can some wizards maybe share a hat?'s starting to get really hard to find an optimal algorithm or method to solving complete graphs. Maybe we can shift our focus to other types of graphs.


Whereas with the complete graphs, finding an optimal strategy got more and more difficult, with cycles things are really nice. We can prove that for any cycle with six or more vertices, the best score is always 2. Recall that there are no asymmetric graphs with five or fewer vertices, so this only holds for cycles with more than five vertices.

Optimal way to anisocrate a cycle graph
Theorem 2. For any cycle graph with more than five vertices, the best score is 2.
Proof. We'll first want to show that no cycle has a best score of 1, i.e. adding an edge won't make a graph asymmetric. Well, if such an edge connected v and w, then there would be an automorphism that moves v to w and w to v (think reflectional symmetry still exists in the graph).
We can now show a two-move strategy that always works on cycles. Consider some node v, and call the node two places to the right v+2 and the one three places to the right v+3. Connecting an edge from v to v+2 and an edge from v to v+3 creates an asymmetric graph. To prove this, suppose there existed some automorphism A of this graph. Notice that v has degree 4, v+2 and v+3 both have degree 3, and all else has degree 2. By nature of automorphisms, A(v) = v (A must fix v), since there is no other vertex of degree 4. Now, A must either fix v+2 and v+3, or swap them. If A doesn't fix them, then we can see that distance between v+2 and v is 2, while the distance between v+3 and v is 3 from one direction and at least 3 in the other direction. Since automorphisms preserve distance between vertices and fixed points, this isn't possible. If A fixed v+2 and v+3, then we can see that all other nodes must be fixed, and we're left with the trivial automorphism. Thus, the only possible automorphism is the trivial automorphism, and the graph is asymmetric. \(\Box\)

Complete Balanced Binary Trees

Bean doing yoga tree pose
A balanced bean-ary tree.

Complete balanced binary trees (BBTs or perefect binary trees) are an interesting specimen here. They are both super simple structures and rich in symmetry. With just the fifth tree, which has \(2^5 - 1 = 31\) vertices, we get a whopping 32,768 automorphisms! Intuitively, at least for me, the simple structure and rich symmetry conflicted, so I didn't know what to expect in terms of best possible score. But we can notice something crucial: we kind of only have to worry about the leaf nodes. And actually only every pair of leaf nodes. That is, if we don't add an edge to a leaf node or add an edge to its sibling, then an automorphism exists that just swaps that leaf node with its sibling. Let's call \(\gamma_n\) the lowest possible score for a balanced binary tree with \(2^n-1\) nodes. Then \(\gamma_n\) is at least a quarter of the number of leaf nodes (the number of edges it would take to make sure each leaf or its sibling has an added edge). Well, this is just \(2^{n-2}/2 = 2^{n-3}\). So \(2^{n-3} \leq \gamma_n\).

Here is a strategy for guaranteeing \(\gamma_n \leq 2^{n-2}-1\):

Unoptimal solution for any BBT
And it's true we can shave off a couple of these lines. But, as we'll see, there might be a better way to do it.

So, we have our score bounded by \(2^{n-3} \leq \gamma_n \leq 2^{n-2} - 1\). But consider the following strategy:

A better solution to BBTs

It seems visually clear that this should always work, so I'll forgo a proof, perhaps writing it up at a later time. But this means that \(\gamma_n = 2^{n-3} + 1\). And we can reason that we can't do any better than that, i.e., we can't anisocrate a balanced binary tree of \(2^n-1\) nodes in only \(2^{n-3}\) edges. Well, if this were the case, this would only be able to connect every pair of leaves to some other pair of leaves. You can check that we can always swap some nodes' children to yield an automorphism.

Kill Ratio

In studying balanced binary trees, we saw something really cool: the fifth BBT had 31 nodes and took only 5 edges to anisocrate. Amazingly, those 5 added edges killed 32,768 automorphisms! We can consider what I'll call the 'kill ratio' of that binary tree: the ratio between the number of starting automorphisms and least number of edges needed to anisocrate, \(\frac{32,768}{5} = 6,553.6\). What is the kill ratio for any BBT? And can we find a better kill ratio?

Firstly, what are we really looking for? Let's define the kill ratio of a graph G as \(R_G = \frac{|Aut(G)|}{\lambda_G}\), where \(\lambda_G\) is the best possible isocration score. For reasons explained here, the number of automorphisms of a BBT with \(2^n-1\) nodes is \(2^{2^{n-1}-1}\). Combining that with what we found in the last section, we get a function that describes the kill ratio of a BBT with \(2^n-1\) nodes: \begin{align}R_{\text{BBT}_n} = \frac{2^{2^{n-1}-1}}{2^{n-3}+1}.\end{align}

This function grows really fast, so the larger the BBT, the greater the kill ratio. And that's really cool, because you can have so many automorphisms broken with so few edges. In other words, symmetry is fragile.

So what about other types of graphs? We saw that cycle graphs (for \(n>5\)) can always be anisocrated in two edges. For some \(n\), an \(n\)-cycle has \(2n\) automorphisms, so \begin{align}R_{n\text{-cycle}} = \frac{2n}{2} = n.\end{align} This is really nice! It's kind of a linear baseline for comparing other kill ratios. For now, let's look at only those graphs that can be optimally anisocrated with just new edges. How do other graphs compare?


We'll look at the kill ratio of graphs of n vertices with no edges, what I like to call archipelagos. When \(n>6\) we have an easy strategy to always ensure a score of \(n-1\) (for \(6 < n <1 5\), I think this is optimal). We can simply form a graph of the form:

General archipelago solution

This isn't optimal for \(n\geq 15\), though, since we can make one of these graphs with 7 vertices and one of these graphs with 8 vertices, saving us an edge. Let's focus on the unoptimal \(n-1\), since that extra edge hopefully won't affect us too much. So, how many automorphisms are there of an n-chipelago? Well, the vertices are allowed to permute freely, so there are \(n!\) combinations. That gives us a kill ratio of \begin{align}R_{n\text{-chipelago}} = \frac{n!}{n-1} = n\cdot(n-2)!\end{align}

This kill ratio is the best yet!

Desmos comparison of the Kill Ratio functions seen so far
Comparing kill ratio functions of archipelagos [blue], BBTs [red], and cycles [green]. Notice the change in variable in the BBT function. Graphed using Desmos.

I think that maybe probably possibly any other family of graphs have kill ratios between these cycles and archipelagos. A 'family of graphs' is kind of non-rigorous term, so let's just say it's a set of 'similar' graphs that has only one graph of n vertices for any number n, up to isomorphism. This way, we're able to push the non-rigor from 'family' to 'similar'.

Conjecture 2. Any family of graphs has a kill ratio function that eventually resides between that of cycles and archipelagos.

Summary and Open Questions

We started with a dream of finding a function that takes in the number of starting nodes of a graph and tells us whether we could have done a better job anisocrating the graph or not in hopes of being a better NAP player. We called this function W(n) and found the upper bound \begin{align}W(n) \leq\frac{3n^2 - 7n + 2}{2}\end{align} by analyzing complete graphs. So, for example, if we started with five nodes and scored 22, then we know we could've done better, since our bound says \(W(5)\leq21\). But we found ways to keep optimizing this strategy and shave off points. Describing functions for these strategies proved harder and harder, and showing one strategy was optimal felt even harder.

We moved on to solve more specific kinds of graphs. Cycles proved to be really easy, as we can always anisocrate them with two edges. BBTs are nice too, since we can also strictly use edges, and only use \(2^{n-3}+1\) edges. This made us curious about the starting-automorphism-count-to-optimal-anisocration-score ratio. This ratio is a sort of metric for measuring the fragility of a graph's symmetry. For cycles, it's really nice, since that ratio is equal to how many nodes are in the cycle. The BBTs have a pretty good one; its exponential growth shows that its symmetry is very fragile. We then saw that a group of unconnected vertices, which we called archipelagos, had an extremely steep kill ratio function.

I'm still very curious about this game. Aesthetically, the notion of optimally adding to a graph to break all its symmetries is beautiful and fun and tells us a lot about symmetry. In practice, I think it's just really fun. And in practicality, I think studying this asymmetry may have some implication in group theory by way of Frucht's Theorem, which I'll write about in the future. The asymmetry of graphs is also important in logic trees and SAT solvers in formal methods. All in all, studying the symmetry and asymmetry of this game and these graphs lead to very interesting things and leave me with many questions...

I would love to receive ideas, proofs, counterexamples, mistakes, etc. on any of the topics here, especially Conjecture 1 and Conjecture 2, as well as better or even optimal strategies for anisocrating complete graphs, a function that more accurately describes optimal anisocration of archipelagos, and definitely a tighter bound on W(n). You can send any of this and more to my email: ian [at] beanway [dot] me.

Antler and Hat wizard making a asymmetric graph!
The Wizards of Asymmetry!