# Graph automorphism group

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?

• No, not all permutations satisfy that (unless $G$ is a complete graph, or an edgeless graph). – 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.