The Petersen Graph

This funky looking graph is called the Petersen graph, and is quite a famous one in the field of graph theory. Naturally, I wanted to see if it was graceful, so I created a program on my computer to try and check. And it was! In fact, I was able to generate all possible graceful labelings on the Petersen graph, which produced some interesting results.

Firstly, the Petersen graph has 72 distinct sets of vertex labels that can generate a graceful labeling. Diving a little deeper, we might want to talk about how many labelings can come from each label set. However, you might notice that the Petersen graph looks pretty symmetrical; you can rotate it, flip it, and do many more actions on it and leave the graph looking the same. So if we construct one labeling, and then rotate it, we can think of those two as really the same thing:

These two graceful labelings are just rotations of each other; note that in each graph, any given vertex is still connected to the same ones it was before the rotation. So 2 is still connected to 3, 13, and 14, and 0 is still connected to 9, 14, and 15, and so on. We call such a transformation that leaves a graph looking the same an automorphism. It turns out the Petersen graph has 120 of these; meaning given any labeling, we can make 119 other equivalent labelings!

When I generated all of the labelings, I kept track of how many labelings I was getting from each label set. For the majority of the label sets that could produce a graceful labeling, there were 120 generated labelings; that is, really just one labeling, and its 120 automorphisms. It shouldn't be an unreasonable thought, then, given how structured and symmetrical the Petersen graph is, that this would be true for every label set. BUT! Dear reader, I was WRONG:

Here, we see two graceful labelings of the Petersen graph, using the same vertex labels, but they are not automorphisms of each other! Note, for example, in the left graph, the vertex labeled 2 is connected to 3, 13, and 14, but in the second graph, it is connected to 0, 3, and 13! So this label set actually generated two totally different labelings! And it wasn't the only one to do this, either; out of the 72 total label sets that can produce a graceful labeling, 12 of them also exhibited this strange behavior. On top of that, there seemed to be no pattern between the two labelings; how they differ from each other varies from label set to label set!

As of the time of writing, it's still unclear as to why the Petersen graph, or any other graceful graph for that matter, might have this characteristic. If you can think of any reasons why, I'd love to hear it (and so would all the other nerds who study this stuff)!