# 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$
Title graph isomorphism GraphIsomorphism 2013-03-22 12:16:24 2013-03-22 12:16:24 vampyr (22) vampyr (22) 5 vampyr (22) Definition msc 05C60 isomorphism isomorphic Graph Digraph GraphHomomorphism