graph isomorphism

A graph isomorphism is a bijection between the vertices of two graphs $G$ and $H$ :

f:V(G)\rightarrow V(H)

with the property that any two vertices $u$ and $v$ from $G$ are adjacent if and only if $f(u)$ and $f(v)$ are adjacent in $H$ .

If an isomorphism can be constructed between two graphs, then we say those graphs are isomorphic.

For example, consider these two graphs:

\xymatrix{a\ar@{-}[r]\ar@{-}[rd]\ar@{-}[rdd]&g\\ b\ar@{-}[ru]\ar@{-}[r]\ar@{-}[rdd]&h\\ c\ar@{-}[ruu]\ar@{-}[r]\ar@{-}[rd]&i\\ d\ar@{-}[ruu]\ar@{-}[ru]\ar@{-}[r]&j}

\xymatrix{1\ar@{-}[rrr]\ar@{-}[rd]\ar@{-}[ddd]&&&2\\ &5&6\ar@{-}[ur]\ar@{-}[l]\ar@{-}[d]&\\ &8\ar@{-}[u]\ar@{-}[r]\ar@{-}[dl]&7&\\ 4&&&3\ar@{-}[uuu]\ar@{-}[lll]\ar@{-}[ul]}

Although these graphs look very different at first, they are in fact isomorphic; one isomorphism between them is

f(a)=1

f(b)=6

f(c)=8

f(d)=3

f(g)=5

f(h)=2

f(i)=4

f(j)=7