I am not so sure about the difference between an isomorphism and automorphism. Consider the two graphs below:
It is my understanding that these two graphs are isomorphic, as we can create a permutation,
$$\begin{array}{rcl}
1 & \mapsto & 1\\
2 & \mapsto & 2\\
3 & \mapsto & 4\\
4 & \mapsto & 3
\end{array}$$
These are the labels that switch in the isomorphism. Are these graphs “automorphic?” (Is that a word?) If so, what would be an example of two graphs that are isomorphic but not automorphic. If these two are not “automorphic,” why? Since the morphism forms the “same” graph, what is the difference?
Thank you.
Best Answer
An automorphism is an isomorphism, which goes from an object to itself.
Formally the first graph is given as $(\{1,2,3,4\},\{12,24,34,13\})$ (using the shorthand $12$ instead of the formally correct $\{1,2\}$ for the sake of readability), while the second graph is given as $(\{1,2,3,4\},\{12,23,34,14\})$. Both graphs have the same set of vertices, but different sets of edges, so they are distinct. Thus is doesn't make sense to ask, whether they are automorphic.
However, as you noted the function $1 \mapsto 1, 2\mapsto 2, 3\mapsto 4, 4\mapsto 3$ gives a welldefined isomorphism of the left graph to the right one. In fact, for this to be true it is crucial, that we have the different choice of edges (because considering this function as a map from the first graph to itself would rip apart edges and insert new ones, i.e. it is not a homomorphism of graphs)!
An example of a nontrivial automorphism of the second graph would be the map $1 \mapsto 2, 2 \mapsto 3, 3 \mapsto 4, 4 \mapsto 1$.