I am studying discrete mathematics and graph theory and I came across a question about asymmetry that I couldn't solve:

Show that a graph with n vertices is asymmetric if and only if n! distinct graphs on the set V(G) are isomorphic to G

I had two concerns: the first was minor:

I tried assuming that the graph with n vertices is asymmetric and then used the fact that an automorphism of a graph G = (V,E) is any isomorphism of G and G, i.e. any bijection f : V → V such that {u, v} ∈ E if and only if {f(u), f(v)} ∈ E.

Then, I basically wrote the set V(G) as {1, 2, 3....., n} and showed that there were n! ways to rename the vertices, but I wasn't sure if it was a guarantee that these new graphs with differently named vertices were actually distinct graphs.

2nd Concern:

To show that the other direction is true, ie. assuming that there are n! distinct graphs on V(G) isomorphic to G and proving that the graph is asymmetric.

I figured that there must at least be n! distinct graphs on V(G) isomorphic to G since simply changing the names of the vertices would give n! distinct vertices. But now I'm stuck since I am not sure how to show that the only automorphism is the identity map.

Would anyone please try to see if there is anything wrong with my assumption in the first concern and how to proceed with the second? Thanks!

  • 1
    $\begingroup$ For your first concern: If two of your graphs are the same graph, then you've found a nontrivial isomorphism of the original graph. For your second concern: The identity map ALWAYS preserves the graph. If you have a non-identity that preserves the graph, then you have a symmetry in the graph. $\endgroup$ – Christopher Carl Heckman Apr 4 '16 at 7:05
  • $\begingroup$ Thanks for your reply! So for the first concern, am I correct in assuming that shuffling the name of the vertices actually gives rise to different graphs? As for the second concern, I still don't understand how I actually should show that the identity is the only map from the fact that there are only n! distinct graphs on V(G)? I am also not able to show that I cannot find a non-identity that preserves the graph. $\endgroup$ – mathmonk Apr 4 '16 at 7:13
  • $\begingroup$ Let's pick $n=3$ for an example. If $\pi = (p_1,p_2,p_3)$ and $\rho=(q_1,q_2,q_3)$ are permutations of $(1,2,3)$ such that the graph with vertices labelled as $p_1$ in place of $q_1$, $p_2$ in place of $q_2$, and $p_3$ in place of $q_3$ is identical to the original graph, then the permutation that sends $p_i$ to $q_i$ is in the automorphism group. Also, if $\pi\not=\rho$, then at least one of them is not the identity. $\endgroup$ – Christopher Carl Heckman Apr 4 '16 at 7:22

The first concern has been adequately dealt with in the comments.

For the second part, assume without loss of generality that $V(G) = \{1,\ldots,n\}$ holds and let $\mathcal G$ denote the set of graphs on $\{1,\ldots,n\}$ isomorphic to $G$. We have $|\mathcal G| = n!$ by assumption. Choose for each $H\in\mathcal G$ an isomorphism from $H$ to $G$, that is, a bijection $f_H : \{1,\ldots,n\} \to \{1,\ldots,n\}$ such that $\{u,v\} \in E(H)$ holds if and only if $\{f_H(u),f_H(v)\} \in E(G)$.

Let $S_n$ denote the set of bijective functions $\{1,\ldots,n\} \to \{1,\ldots,n\}$. (Also known as the symmetric group on $n$ elements.)

Proposition. The map $\varphi : \mathcal G \to S_n$ given by $H \mapsto f_H$ is injective.

Proof. Let $H,H'\in\mathcal G$ be given with $H \neq H'$. Thus, now there are some $u,v\in\{1,\ldots,n\}$ with $\{u,v\} \in E(H)$ and $\{u,v\} \notin E(H')$. Therefore we have $$\{f_H(u),f_H(v)\}\in E(G) \qquad \text{and} \qquad \{f_{H'}(u),f_{H'}(v)\} \notin E(G). $$ Thus, in particular we have $\{f_H(u),f_H(v)\} \neq \{f_{H'}(u),f_{H'}(v)\}$, so we must have $f_H(u) \neq f_{H'}(u)$ or $f_H(v) \neq f_{H'}(v)$, or possibly both. This shows that $f_H \neq f_{H'}$ holds.$\hspace{2mm}\blacksquare$

We find that $\varphi$ is an injective function from two sets of size $n!$ so it follows that $\varphi$ is in fact a bijection. Therefore $\varphi^{-1}$ exists and is bijective. Now let $\text{id} \in S_n$ denote the identity permutation $v \mapsto v$. For any non-trivial permutation $\pi \in S_n \setminus \{\text{id}\}$ we have $\varphi^{-1}(\pi) \neq \varphi^{-1}(\text{id}) = G$, by injectivity of $\varphi^{-1}$, so applying the permutation $\pi$ to the graph $G$ yields a distinct graph on the vertex set $\{1,\ldots,n\}$. This shows that $\pi$ is not an automorphism of $G$.

Side note: if you know the language of group actions, the entire proof can be simplified by using the orbit-stabiliser theorem. Let $S_n$ act on the set of all graphs on $V(G)$, then the automorphism group of $G$ is precisely its stabiliser. Furthermore, the orbit of $G$ is precisely the set of distinct graphs on $V(G)$ that are isomorphic to $G$. By the orbit-stabiliser theorem, we have $$ \big|\text{stabiliser}(G)\big|\cdot \big|\text{orbit}(G)\big| = n!. $$ In particular the stabiliser (and hence the automorphism group of $G$) is trivial if and only if the orbit contains $n!$ elements.


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.