About NAPsmall graph

I just released a little puzzle game called NAP (short for No Automorphisms, Please). The goal is to add vertices and edges to the existing graph to give it a trivial automorphism group, i.e., break all of its symmetries. Doing so with fewer edges and vertices yields a higher score.

graph shaped like a smiley face :)

I was inspired by an exam problem in my graph theory course this past semester. The problem was something along the lines of

                
Find a finite, 4-regular graph with trivial automorphism group.
                
            
Typically, the exam problems are proof-oriented or a question with a narrower path. But the process of solving this, at least the way I did it, felt very much like a puzzle game. You just have to start, and then you reason about where that got you, and go down a different path; but oh! you just found out that path doesn't work, so you backtrack and try again. It's a very interactive, maze-like, get-your-hands-dirty kind of problem with an experience only justafiable by actually doing the problem (go ahead and try it). So I took the idea and made a mini daily puzzle game.

How do you calculate graph automorphisms?

You ask someone else do to calculate them, of course! In this case, that someone is Sage, and specifically the SageMathCell API. In general, it takes some heuristic and some brute force. One goal of this game is to help develop these two geometric senses.

Pretty graphs!!!!

I agree! That's how you know I didn't make them! The interactive graph display is vis js, a really handy Javascript library. Making vis js and Sage play nice, however, was a lot harder than it seems.

Try It

Go try the game! There's a new puzzle every day. At time of writing, the game is in version 1.0.0.