I am bit confused about some conventions about how this counting is done in different literatures. Say one is given a graph on $n$ vertices labelled, $a_1,a_2,…a_n$. Now isn't any of the permutations of the labels of the graph a distinct isomorphic copy of the graph? And hence there are $n!$ isomorphic copies of a graph. Right?
I am using the definition that graphs $G_1$ and $G_2$ are isomorphic iff there is a bijective function $f : V(G_1) \rightarrow V(G_2)$ such that $(x,y) \in E(G_1)$ iff $(f(x),f(y)) \in E(G_2)$
Hence any permutation of the labels of the graph naturally gives such a $f$ and hence the relabelled graph is isomorphic to the original one. Right?
Best Answer
What you claim is that an automorphism of a graph is simply a bijection of its set of vertices to itself. But note that there is an extra condition (which makes an isomorphism more than a bijection), namely that the bijection should also preserve the edges (in general this is preserving the structure of the space).
Your claim is true for complete graphs though (why?).
To further illustrate this, take the following example: Take the simple graph $G$ with three vertices and two edges: $a-b-c$.
Edit: Let us see why $|Aut(G)|=2$. Let $f\in Aut(G)$. Suppose $f(b)\neq b$. Wlog, set $f(b):=c$. $ab$ and $bc$ are the edges of $G$. As $f$ is an automorphism, we must have $f(a)f(b)$ and $f(b)f(c)$ to be the edges of $G$ as well. But this cannot happen since $f(b)=c$ has exactly one edge attached to it. Thus $b$ is a fixed point of $f$. Further, there are two automorphisms of the graph, namely the identity and the one that changes the places of $a$ and $c$. Hence the result follows.