By Wikipedia,

an automorphism of a graph $G = (V,E)$ is a permutation $\sigma$ of the vertex set $V$, such that the pair of vertices $(u,v)$ form an edge if and only if the pair $(\sigma(u),\sigma(v))$ also form an edge.

Don't all permutation satisfy that? If we take a random permutation of the vertex set and apply it to the vertex labels, we end up with an isomorphic graph. So how is the automorphism group any different than the group of all permutations of the vertex set?

  • 1
    $\begingroup$ No, not all permutations satisfy that (unless $G$ is a complete graph, or an edgeless graph). $\endgroup$ – Angina Seng Jun 19 '18 at 5:23

As a simple counterexample, take a graph on $3$ vertices, with one isolated vertex $u$, and two adjacent vertices $v,w$.

Every automorphism must fix $u$, and permute $v,w$, so not every permutation is an automorphism.

Perhaps your misunderstanding is this . . .

It's true that given an arbitrary permutation of the vertices, if you apply the permutation to the vertices, and also permute the corresponding edges (i.e., change the old edges to new ones based on the permutation), then the new graph is isomorphic to the old one.

But by definition, an automorphism is a permutation of the vertices that maps edges to corresponding edges without changing the edges (i.e., with no change with regard to which vertices are adjacent).

| cite | improve this answer | |

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.