Изоморфизм графов. Попарно неизоморфные (p,q)-графы.
Графы G1=(V1,E1) и G2=(V2,E2) называются изоморфными, если существует биекция j: V1®V2, которая сохраняет отношение смежности между вершинами графа:
"u,vÎV1 ({u,v}ÎE1Û{j(u),j(v)}ÎE2).
В следующем примере биекция 
является изоморфизмом графов.
Графы G1=(V1,E1) и G2=(V2,E2) могут быть неизоморфными, если:
1) 
;
2) 
;
3) для каждого 
графы имеют различные числа вершин степени 
.
Графы могут быть неизоморфными, даже если все перечисленные три условия выполнены:
