Графы G 1=(V 1, E 1) и G 2=(V 2, E 2) называются изоморфными, если существует биекция j: V 1® V 2, которая сохраняет отношение смежности между вершинами графа:
" u, v Î V 1 ({ u, v }Î E 1Û{j(u),j(v)}Î E 2).
В следующем примере биекция является изоморфизмом графов.
Графы G 1=(V 1, E 1) и G 2=(V 2, E 2) могут быть неизоморфными, если:
1) ;
2) ;
3) для каждого графы имеют различные числа вершин степени .
Графы могут быть неизоморфными, даже если все перечисленные три условия выполнены: