What is the difference between automorphism and isomorphism of a graph in graph theory?

Question

Please explain with an example the difference between automorphism and isomorphism of a graph.

Answer 1

Here's a vertex-labelled graph:

An isomorphism is a relabelling of its vertices, e.g.:

An automorphism is a relabelling of its vertices so that you get the same graph back again (i.e., the same vertex set, and the same edge set), e.g.:

Vertex set: $\{0,1,2,3,4,5\}$ and edge set: $\{01,02,03,04,45\}$, just as in the original graph.

An automorphism is a permutation of the vertex set that maps edges to edges and non-edges to non-edges. So in the above example, the automorphism is the permutation $(0)(132)(4)(5)$.

Answer 2

There is a general difference, for all contexts, and a specific point to note about the terms used for graphs.

Generally an automorphism is a special case of isomorphism when an entity is mapped to itself. So, for example, a field automorphism is an isomorphism of the field with itself. It's not surprising that such a thing exists, since the identity map is one such isomorphism, but there are often additional automorphisms (and the automorphisms of an entity form a group under function composition).

Regarding graphs specifically, one again has the sense that automorphism means an isomorphism of a graph with itself. But there is something to note here. We sometimes consider graphs with vertices "labelled" and sometimes without labelling the vertices. In the latter case we are considering graphs as distinct only "up to isomorphism".

Thus to talk about automorphisms of graphs we necessarily would consider the vertices to be labelled, because otherwise (with unlabelled vertices) the notion of automorphism would be trivial (per the identity map as mentioned above).