What is Graph Isomorphism and Graph Invariant?

Question

While I was reading Reinhard Diestel text on graphs, I came across this paragraph.

Let G = (V, E) and G' = (V' , E' ) be two graphs. We call G and G' isomorphic,and write G $\simeq $ G' , if there exists a bijection φ: V → V with xy ∈ E $ \leftrightarrow $ φ(x)φ(y) ∈ E for all x, y ∈ V . Such a map φ is called an isomorphism; if G = G' , it is called an automorphism.

We do not normally distinguish between isomorphic graphs. Thus, we usually write G = G' rather than G $ \simeq $ G , speak of the complete graph on 17 vertices, and so on.

A map taking graphs as arguments is called a graph invariant if it assigns equal values to isomorphic graphs. The number of vertices and the number of edges of a graph are two simple graph invariants; the greatest number of pairwise adjacent vertices is another.

What does this paragraph mean and what are graph invariants, in simple explanations.

Answer 1

In simple terms, two graphs are isomorphic to each other so long as there is a bijection between the two vertex sets and such that the bijection preserves edges. That is, two graphs $G$ and $G'$ are isomorphic if there exists a bijection, $\phi: V(G) \to V(G')$, and if that bijection also preserves edges. Explicitly, this means that if $uv$ is an edge in $E(G)$, then $\phi (u) \phi (v)$ is an edge in $E(G')$.

One can visualize a graph isomorphism in two ways. 1. Start with a graph and move around vertices in what ever way you want while keeping all the edges in tact. The result, a graph that looks different, but isn't really. 2. A re-labeling of the vertices of $G$. This produces a graph that looks the same, but the vertices are called something else.

Automorphisms are a little bit trickier. The way I look at an automorphism is a moving around of vertices (while keeping edges in tact, as in (1) above) with the caveat that the graph must look exactly the same as before. For example, take $C_4$ with vertex set $V(G) = u_1,u_2,u_3,u_4$ and edge set $E(G) = u_1u_2,u_2u_3,u_3u_4,u_4u_1$ and consider the following bijection.
1. $\phi: V(G) \to V(G')$ where $\phi$ is the permuation $(u_1u_2u_3u_4)$ that sends $u_1 \to u_2$ $u_2 \to u_3$ $u_3 \to u_4$, and $u_4 \to u_1$. (If one is unfamiliar with cycle notation). This is an isomorphism since every edge is preserved, and indeed it is also an automorphism since the resulting graph looks exactly the same as the regular graph. (the permuation above is really just a rotation by 90 degrees if you lay out the original as a "square", as is tradition.