Graph automorphism group

288 Views Asked by At

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

There are 1 best solutions below

0
On

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