Graph isomorphisms are extremely interesting to me, but I didn't sit down to write about the hardness of the problem, or the fun fact that you can test for isomorphism in a "constant" number of queries (very dramatic air quotes around "constant" here, but it is independent of graph size, so you can dedupe your copies of the entire internet if you'd like.) Instead, I want to share one isomorphic family, the graphs on 7 vertices and 5 edges. I could get these pretty quickly by enumerating all graphs, and found they hit a perfect sweet spot for making silly faces.
When I first found these I was interested in the size of these isomorphism classes, in particular: given \(v=|V|\) vertices, and \(e=|E|\) edges, how many distinct isomorphs are there?
I created these in Julia using the Graphs, Combinatorics, and Plots libraries, I did it very naively by enumerating all graphs, and then checking them against a set of distinct graphs I had found so far. For bigger graphs, you may want to do something similar, but then also generate all relabling's of that graph to filter them. I would love to know of a smarter way to generate them, I can't imagine it is trivial. The image is freely available on the Wikimedia Commons, or just download it here.
