[Math] Understanding graph automorphism as opposed to isomorphism.

combinatoricsgraph theorygraph-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?

Best Answer

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

To answer the question in your edit, this does not depend on whether the two graphs have the same vertex set.

Related Question