# Understanding graph automorphism as opposed to isomorphism.

Consider the simple path graph, $P$ over vertices labeled from $1$ to $n$. If all path graphs over $n$ vertices are isomorphic to $P$ (I can relabel the vertices in $n!$ ways and still have the same graph.), then why does $P$ have only 2 automorphisms?

Edit: Is the explanation related the fact that there is only one vertex set to map vertices from?

While you can label the vertices of a path graph in $n!$ different ways, most of of these labelings do not correspond to isomorphisms between the graphs. For example, if the vertex labelled by $1$ in the first graph were one an end of the path but was not on the end in the second graph, any map that sent vertex $1$ in the first graph to vertex $1$ in the second graph would not be an isomorphism since isomorphisms cannot map a vertex in the first graph to a vertex in the second graph that has a different degree. So from your $n!$ ways of labeling the graphs, you obtain $n!$ graphs which are all isomorphic, but there are just two isomorphisms between any given pair of these graphs.
In fact, the number of isomorphisms between two isomorphic graphs is always equal to the number of automorphisms of one of the graphs. This is because if $X$ and $Y$ are graphs, $\mathrm{Aut}(X)$ is the automorphism group of $X$ and $\phi : X \rightarrow Y$ is an isomorphism, then the coset of all isomorphisms from $X$ to $Y$ is $\phi \circ \mathrm{Aut}(X) = \{\phi \circ \sigma \vert \sigma \in \mathrm{Aut}(X)\}$. Clearly, this set has the same cardinality as $\mathrm{Aut}(X)$. (Actually, this last paragraph holds not just for graphs but for just about any mathematical object you can imagine.)
• I see now that it follows from the definition that an isomorphism does not map vertices having different degrees. But then how does isomorphism encapsulate the notion of 'sameness' of two graphs(i.e. "Is graph $A$ superimposable on a graph $B$(nevermind the vertex labels)?")? – Akay Feb 16 '17 at 9:53