Dois grafos, G e H, são isomorfos se existe uma bijeção do conjunto de vértices de G no conjunto de vértices de H que preserva adjacências.  Assim, se a bijeção é b então, para cada par v w de vértices de G, devemos ter

v-w é arco de G
se e somente se
b(v)-b(w) é arco de H.