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$. enter image description here

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$)

  • 2
    $\begingroup$ You cannot say since each vertex has $3$-edges incident with it, therefore the graphs are isomorphic. To see why consider the Petersen Graph and the pentagonal prism. These graphs are $3$-regular and have 10 vertices but are not isomorphic. $\endgroup$ – Ben Dec 29 '15 at 22:45
  • $\begingroup$ @Ben Got it. Any idea on part (ii)? $\endgroup$ – Al Jebr Dec 29 '15 at 22:47
  • $\begingroup$ Based on your hint, you should label the vertices $v$ with $(x,y)$ where $x,y \in (1,\ldots,5)$ and all vertices adjacent to $v$ are labelled $(x',y')$ where $x' \neq x$, $x' \neq y$, $y' \neq y$, $y' \neq x$ and $x', y' \in (1,\ldots,5)$. Then any permutation of the labels with this property is an automorphism. $\endgroup$ – Ben Dec 29 '15 at 22:57
  • $\begingroup$ @Ben I don't understand this part because there are $10$ vertices. Why are we considering a $5$ element set? $\endgroup$ – Al Jebr Dec 29 '15 at 23:05
  • $\begingroup$ We are considering a $5$ element set but we are assigning pairs of elements to each vertex. For example a vertex might be assigned the label $(1,2)$. Then you have $5$ choose $2$ labels which gives $10$ labels. $\endgroup$ – Ben Dec 29 '15 at 23:17

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.

Petersen Graph

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/


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.