Más formalmente, el isomorfismo entre dos grafos G y H es una biyección f entre los conjuntos de sus vértices
[1] Es decir, cualquier par de vértices u y v de G son adyacentes si y solo si lo son sus imágenes, f(u) y f(v), en H. A pesar de su diferente aspecto, los dos grafos que se muestran a continuación son isomorfos:
Dos grafos con matrices de adyacencia respectivas A y B serán isomorfos si y solo si existe una matriz permutación P tal que B = P A Pt.
Este problema admite un ataque por fuerza bruta que exigiría comprobar si las n!
biyecciones posibles preservan la adyacencia, pero no se conoce un algoritmo eficiente, al menos para el caso general.
En este contexto, eficiencia debe interpretarse como crecimiento del número de pasos inferior a O(en).