If n-vertex graph is regular then for automorphism group orbit $O_{v} = n$?

Question

I have a problem with determing orbit $O_{v}$ for automorphism group for Petersens graph. Is that true that $O_{v} = 10$ becouse he is 3-regular, if it is, how to prove it, and if it isn't, how to show that $O_{v} = 10$ in another way for Petersens graph?

Answer 1

For the Petersen graph $\mathcal{P}$, $\text{Aut}(\mathcal{P}) \cong \text{Sym}(5)$. To see this, we begin by using the Kneser Graph definition of $\mathcal{P}$. We have that $V(\mathcal{P}) = \binom{[5]}{2}$, the $2$-element subsets of $[5] = \{1, 2, 3, 4, 5\}$. Now two subsets are adjacent if and only if they have non-empty intersection.

Now for $\sigma \in \text{Sym}(5)$, let $\phi_{\sigma} : V(\mathcal{P}) \to V(\mathcal{P})$ be given by $\phi_{\sigma}(\{a, b\}) = \{ \sigma(a), \sigma(b) \}$. That is, the natural action of $\text{Sym}(5)$ on $[5]$ induces an action on $\mathcal{P}$.

Claim: For each $\sigma \in \text{Sym}(5)$, $\phi_{\sigma} \in \text{Aut}(\mathcal{P})$.

Proof: Exercise.

Claim: For distinct $\sigma, \tau \in \text{Sym}(5)$, $\phi_{\sigma} \neq \phi_{\tau}$.

Proof: Also an exercise.

Based on these two claims, we have at least $120$ automorphisms of $\mathcal{P}$. (Repeated application of the Orbit-Stabilizer Lemma is needed to show that $\text{Sym}(5)$ is actually the full automorphism group).

To show vertex transitivity, you want to show that for any vertex $\{c, d\} \in V(\mathcal{P})$, there exists $\sigma \in \text{Sym}(5)$ such that $\{ \sigma(a), \sigma(b) \} = \{ c, d\}$.

By the way, the Frucht graph is $3$-regular but not vertex transitive. (https://en.wikipedia.org/wiki/Frucht_graph). So in general, regularity does not imply vertex-transitivity.