(i) Show that the drawings in Fig. $1.4$ represent the same graph. (ii) Find the group of automorphisms of the graph in Fig. $1.4$.

Question

From A Course in Combinatorics by van Lint, Wilson:

Problem $1A$: (i) Show that the drawings in Fig. $1.4$ represent the same graph (or isomorphic graphs).

(ii) Find the group of automorphisms of the graph in Fig. $1.4$.

---

For part (i), I first labeled the vertices of both graphs using numbers in a clockwise fashion. Then I relabeled the second graph by following which vertices are connected to other vertices by an edge. Is this a proper technique?

Could I have just said: In both graphs, each vertex has 3 edges incident with it, so they are isomorphic.

---

I am stuck on part (ii). The hint in the back says: Show that the􏰁 $\binom{5}{2}$ 􏰂pairs from $\{1,...,5\}$ can be used to label the vertices in such a way that a simple rule determines when there is an edge. To find the full automorphism group, consider the subgroup that fixes a vertex and its three neighbors. This graph is known as the Petersen graph.

I have found some automorphisms by just rotating the graph. (i.e., $1 \mapsto 2$, $2 \mapsto 3$, $\dots$, $6 \mapsto 7$, $\dots$)

Answer 1

The Petersen graph is a specific instance of a Johnson graph. The Johnson graph $J(\Lambda, S, i)$ is defined with an alphabet of $\Lambda$ elements. The vertices of the graph are the subsets of $\Lambda$ with $S$ elements. Two vertices $v_{i}, v_{j}$ are adjacent if $|v_{i} \cap v_{j}| = i$.

The Petersen graph is constructed as $J(5, 2, 0)$, as shown below.

Recall the definition of graph isomorphism: $\phi : V(G) \to V(H)$ is a bijection and if $ij \in E(G)$, then $\phi(i)\phi(j) \in E(H)$.

Two vertices $v_{i}, v_{j}$ are adjacent in the Petersen graph if they have empty intersection. Thus, any automorphism must preserve this property.

We use the natural group action of $S_{5}$ on $[5] := \{1, ..., 5\}$. It is defined as: $\cdot : S_{5} \times [5] \to [5]$ given by $\sigma \cdot x \mapsto \sigma(x)$ (i.e., take the input $x$ from $[5]$ and map it to its image under the permutation $\sigma$).

We show the action of $S_{5}$ on $[5]$ induces automorphisms of the Petersen graph. Let $\sigma \in S_{5}$ and define a function $\phi_{\sigma} : V(P) \to V(P)$ (where $P$ is the Petersen graph). We take $\{a, b\} \in V(P)$ (where $a, b \in [5]$) and $\phi(\{a, b\}) = \{ \sigma(a), \sigma(b) \}$. Since a permutation is a bijection, we have that $\phi_{\sigma}$ preserves adjacency. I leave it to you to show that $\phi$ is also a bijection.

Let $X = \{ \phi_{\sigma} : \sigma \in S_{5}\}$. We have that $X \leq Aut(P)$. It suffices to show $Aut(P) \cong X$. I leave it to you to show the bijection between $S_{5}$ and $X$.

To show $X$ is the full automorphism group, we use the Orbit-Stabilizer lemma. Let $v \in V(P)$. The Orbit-Stabilizer Lemma gives us that $|Aut(P)| = |\mathcal{O}(v)| \cdot |Stab(v)|$, where $\mathcal{O}(v)$ is the orbit or set of vertices to which $v$ maps under any automorphism. $Stab(v) = \{ \phi \in Aut(P) : \phi(v) = v \}$.

Observe that the orbit of $v = \{1, 2\}$ is $V(P)$. So $|Aut(P)| = 10 \cdot |Stab(v)|$.

Now we apply the Orbit-Stabilizer Lemma again on $Stab(v)$: $|Stab(v)| = |\mathcal{O}(\{3, 4\})| \cdot |Stab(\{3, 4\})|$, where the orbit and stabilizer of $\{3, 4\}$ are considered with $\{1, 2\}$ fixed. We have that $\{3, 4\}$ can map to any of $\{1, 2\}$'s neighbors. So $|Stab(v)| = 3 \cdot |Stab(\{3, 4\})|$.

Iterating on this argument, the remaining neighbors of $\{1, 2\}$ can be freely permuted. So now it suffices to fix a neighbor of $\{3, 4\}$ and we are done.

There are some details for you to fill in, but you may find my blog entry helpful: https://michaellevet.wordpress.com/2015/01/20/automorphism-groups-of-graphs-part-3/