NAP — a game about symmetry

What is NAP?

NAP stands for No Automorphisms, Please!
The goal is to add edges and nodes to the graph to break all symmetries. The fewer added edges and nodes, the better! There's a new puzzle every day.

What counts as a symmetry?

In this case, a symmetry is any 'relabeling' of the nodes that maintains the structure of the graph. If we take some node, we can call the set of all nodes connected to it via some edge its neighbors. Then a symmetry of a graph shuffles some nodes around, but makes sure each node has the same neighbors. Such a symmetry is called an automorphism.
For example, we can label the following graph and its one symmetry. A graph G, with nodes labeled 1-5.An automorphism of G, with nodes 1 and 3 switched. Sometimes, the automorphisms look like the standard symmetry we're used to—reflections and rotations—like how the one above looks like a reflection. But often it can be more subtle and not look like any geometric symmetry. For example, the following is an automorphism that doesn't conform to our standard notion of reflection or rotation:
An arbitrary graphSame arbitrary graph but rotated Note that the actual physical movement of the graph doesn't affect its symmetries, so the following two graphs are the same:
An arbitrary graphSame arbitrary graph but rotated so they have the same symmetries.
This is an example of a graph with no automorphisms (a winning graph!):
an assymetric graph, ie no automorphisms

Manipulating the graph

Click the Edit button, then click Add Node and click anywhere near the graph to add a node. To add an edge, click Add Edge, then drag click your cursor from one node to another. When you think you have a graph with no symmetries, click Check Symmetries! You get 1 point for each edge added and 2 points for each node added. Your goal is to minimize your score.
If a node leaves the screen by accident, you can zoom out (or in) with the navigation buttons.

More about graph symmetries

I break down some math behind graph asymmetries and analyze best possible scores here! Please check it out if you're interested in this game!


Why this game? Firstly, automorphisms are important in so many branches of math, like graph theory, group theory, linear algebra, etc. Developing the intuition for how objects can act on their own and be mapped to themselves is crucial in understanding underlying ideas in these branches of math. The thing I found with automorphisms, though, is that they're not entirely intuitive. I struggled for a long time understanding automorphisms and their importance, so I created this game to try to bridge the understanding-gap of automorphisms in math, through the lens of graph theory. Secondly, I found it really fun and a good geometric exercise. And that on its own makes a game worth making! But with the added pedagogical aspect, this game strives to build an instinct for automorphisms in all branches of math.

The computation is powered by SageCell and the graph interface is powered by vis.js. Code can be found on my Github. Pull requests welcome! :)
Feedback is also welcome: feedback [ at ] beanway [ dot ] me
NAP 1.3.0