What's the difference between the automorphism and isomorphism of graph?

What's the difference between the automorphism and isomorphism of graph?

1. In graph theory, an isomorphism of graphs $G$ and $H$ is a bijection between the vertex sets of $G$ and $H$, $f \colon V(G) \to V(H) \,\!$ such that any two vertices $u$ and $v$ of $G$ are adjacent in $G$ if and only if $ƒ(u)$ and $ƒ(v)$ are adjacent in $H$.

2. In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity.

Could you give a example to explain the difference of the automorphism and isomorphism from the graph $G$ to $G$ itself? Since not all the isomorphism from the graph $G$ to $G$ itself is automorphism.

I have this question when I read this post, please find the key word An isomorphism is a bijective structure-preserving map...and there is a paragraph says that

The graph representation also bring convenience to counting the number of isomorphisms (the pre-factor). For example, for a graph $g$ with $V$ vertices, $E$ edges from some scalar theory, permutation of vertices is equivalent to relabeling of vertices, hence does not change the graph structure. The same goes to permutation of edges. Therefore, the number of graphs isomorphic to $g$ is $V!⋅E!$.

Maybe the isomorphism here does not demand to preserve the vertex-edge realtion, only demand to preserve the structure.

By definition, an automorphism is an isomorphism from $G$ to $G$, while an isomorphism can have different target and domain.

In general (in any category), an automorphism is defined as an isomorphism $f:G \to G$.

• Not all the isomorphism from the graph $G$ to $G$ itself is automorphism. Since automorphism preserving the edge–vertex connectivity. – Eden Harder May 11 '14 at 11:11
• @EdenHarder I don't understand what you mean. An isomorphism is structure-preserving as well, so it preservers the edge-vertex connectivity. – Fredrik Meyer May 11 '14 at 11:26
• Thanks! I update the question. – Eden Harder May 11 '14 at 12:34
• @EdenHarder They key word in the page you're linking to is the word "structure preserving". That means exactly that all the vertex-edge incidences are preserved. – Fredrik Meyer May 11 '14 at 12:48
• Thanks! I update the question. – Eden Harder May 11 '14 at 12:55

As an example, consider the graphs $G$ and $G'$ on 4 vertices, labelled 1, 2, 3 and 4, where $G$ has edge set $\{\{1,2\},\{1,3\},\{2,3\},\{3,4\}\}$ and $G'$ has edge set $\{\{1,4\},\{2,3\},\{2,4\},\{3,4\}\}$. Sketch both of these graphs !

Then the permutation $\alpha = (1, 2, 3, 4)$ (in disjoint cycle notation) is an isomorphism from $G$ to $G'$. Why ? Because, applying $\alpha$ to the vertex labels in the edge set of $G$ we obtain the edge set of $G'$. Check this ! Since an isomorphism from $G$ to $G'$ exists, $G$ and $G'$ are isomorphic. However, since their edge sets are different, $G$ and $G'$ are not equal.

The permutation $\beta = (1, 2)$ is an isomorphism from $G$ to $G$ itself, that is, an automorphism of $G$, also known as a symmetry of $G$. Check this, as above !

• If you are reading this answer and didn't understand that parantheses notation have a look here: youtube.com/watch?v=X4_4Bqj6EdA It basically means map 1 to 2, 2 to 3, 3 to 4 and 4 to 1. – VenkiPhy6 Feb 25 at 5:19

An automorphism of a graph $\Gamma$ is an isomorphism from $\Gamma$ to itself.

• Not all the isomorphism from the graph G to G itself is automorphism. Since automorphism preserving the edge–vertex connectivity. – Eden Harder May 11 '14 at 11:12
• @EdenHarder, an isomorphism takes and edge of $G$ to an edge of $H$ (read the definition that YOU wrote in the question!). Thus every isomorphism from $G$ to $G$ is an automorphism of $G$. BTW, your 2. is an excerpt from Wikipedia entry Graph Automorphism, if you'd have bothered to read the next sentence you would see: "...That is, it is a graph isomorphism from G to itself." – DKal May 11 '14 at 11:27
• Thanks! I update the question. – Eden Harder May 11 '14 at 12:34

If you want to visualize , think about the adjacency matrix of the graph. After applying the automorphism, it will look same as previous.

Say, $A$ is the adjacency matrix of graph $G$ and $P$ is an automorphism matrix (permutation matrix). Then $P^{-1}AP = A$; Here $P$ is an automorphism (informally).