Wed, 07 Feb 2018
The many faces of the Petersen graph
(Actually the Petersen graph cannot really be said to have faces, as it is nonplanar. HA! HA! I MAKE JOKE!!1!)
This article was going to be about how GraphViz renders the Petersen graph, but instead it turned out to be about how GraphViz doesn't render the Petersen graph. The GraphViz stuff will be along later.
Here we have the Petersen graph, which, according to Donald Knuth, “serves as a counterexample to many optimistic predictions about what might be true for graphs in general.” It is not that the Petersen graph is stubborn! But it marches to the beat of a different drummer. If you have not met it before, prepare to be delighted.
This is the basic structure: a blue 5-cycle, and a red 5-cycle. Corresponding vertices in the two cycles are connected by five purple edges. But there is a twist! Notice that the vertices in the red cycle are connected in the order 1–3–5–2–4.
There are different ways to lay out the Petersen graph that showcase its many interesting properties. For example, the standard presentation, above, demonstrates that the Petersen graph is nonplanar, since it obviously contracts to !!K_5!!. The presentation below obscures this, but it is good for seeing that the graph has diameter only 2:
Wait, what? Where did the pentagons go?
Try this instead:
Again the red vertices are connected in the order 1–3–5–2–4.
Okay, that is indeed the Petersen graph, but how does it help us see that the graph has diameter 2? Color the nodes by how far down they are from the root:
Obviously, the root node (black) has distance at most 2 to every other node, because the tree has only depth 2.
Each of the three second-level nodes (red) is distance 2 from the other two, via a path through the root.
The six third-level nodes (blue) are linked in a 6-cycle (dotted lines), so that each third-level node is at most two steps away along the cycle from the others, except for the one furthest away, but that is its sibling in the tree, and it has a path of length 2 through their common parent.
And since each third-level node (say, the one with the red ring) is connected by a dotted edge (orange) to cousins in both of the other branches of the tree, it's only distance 2 from both of its red uncle nodes.
Looking at the pentagonal version, you would not suspect the Petersen graph of also having a sixfold symmetry, but it does. We'll get there in two steps. Again, here's a version where it's not so easy to see that it's actually the Petersen graph, but whatever it is, it is at least clear that it has an automorphism of order six (give it a one-sixth turn):
The 
represents three vertices, one
in each color. In the picture they are superimposed, but in the actual
graph, no pair of the three is connected by an edge. Instead, each
of the three is connected not to the others but to a tenth vertex that
I omitted from the diagram entirely.
Let's pull apart the three vertices
and reveal the hidden tenth vertex
and its three edges:
Here is the same drawing, recolored to match the tree diagram from before; the outer hexagon is just the 6-cycle formed by the six blue leaf nodes:
|
|
But maybe it's easier to see if we look for red and blue pentagons. There are a couple of ways to do that:
| 
|
As always, the red vertices are connected in the order 1–3–5–2–4.
Finally, here's a presentation you don't often see. It demonstrates that the Petersen graph also has fourfold symmetry:
Again, 
and 
represent single vertices stretched out
into dumbbell shapes. The diagram only shows 14 of the 15 edges; the
fifteenth connects the two dumbbells.
The pentagons are deeply hidden here. Can you find them? (Spoiler)
Even though this article was supposed to be about GraphViz, I found it impossible to get it to render the diagrams I wanted it to, and I had to fall back on Inkscape. Fortunately Inkscape is a ton of fun.
[Other articles in category /math] permanent link