グラフ同型
G {\displaystyle G} の任意の2頂点 v , w ∈ V {\displaystyle v,w\in V} に対して, ( v , w ) ∈ E {\displaystyle (v,w)\in E} となるのが ( f ( v ) , f ( w ) ) ∈ E ′ {\displaystyle (f(v),f(w))\in E'} となるとき、かつそのときに限るような V {\displaystyle V} から V ′ {\displaystyle V'} への全単射写像 f {\displaystyle f} が存在するとき, G {\displaystyle G} と G ′ {\displaystyle G'} はグラフ同型(あるいは単に同型)であるといい、 G ′ {\displaystyle G'} は G {\displaystyle G} の同型グラフであるという。
例として以下のようなグラフが与えられたとする。
このとき、隣接する頂点に対応する頂点は隣接していることがわかる。 このように G {\displaystyle G} と G ′ {\displaystyle G'} が「同一」の頂点を持ち、同一の辺のつながりかたをしているときにそのグラフを同型というのである。