These Two Graphs Do This

I’ve been doing some academic research lately that involves computing the probability that a network that grows by adding links in a particular way will end up with certain properties. I went about this by generating all graphs up to a particular order, and so I used unlabeled graphs, which seemed good enough and meant I had far fewer graphs to deal with.

Eventually I decided that it would be more realistic to at least pretend that the computation was being done on labeled graphs (by making sure that I got the same answer either way). This led me to a discovery that wasn’t too surprising by itself, but I was surprised that I hadn’t thought of it earlier: there are (unlabeled) graphs for which adding two completely different edges will produce the same graph. For illustration I found the smallest example:

The first thing to notice about this graph is that it’s completely asymmetric: The pink and orange vertices have the distinction of being the only degree-4 and degree-2 vertices respectively. The blue vertex is distinguished as being the only vertex adjacent to both the pink and orange. The green vertex is the only degree-1 vertex adjacent to the pink, and the yellow and blue vertices are clearly distinct from each other as they have different degrees. So there is no symmetry in this graph whatsoever, which means that any edge we could conceivably add to it would be “different” from any other edge we could add.

So there are two different edges we can add to this graph and end up with graphs that are isomorphic to each other. Specifically, by adding either edge we will end up with this graph:

Another way to say it is that our original colored graph is a subgraph of this graph in two different ways. This can be easily illustrated by repositioning the vertices so they match the supergraph in two different ways:

You should be able to confirm visually that these two are the same as the original graph, and that they can each be transformed into the supergraph by adding a single edge, which is drawn dashed.

So this is the smallest pair of graphs that has this property, and in fact the only example on six vertices. I’m not sure how common they are. It is not a straightforward thing to google.

Another cool thing is that, apparently just by coincidence, the smaller graph and the larger graph are complements of each other. So if we take the original graph and reverse all the links like so:

we end up with the same graph that we got by adding an edge:

Kinda weird.