En el artículo An Efficient Algorithm for Graph Isomorphism de Corneil y Gotlieb, 1970, se estableció una conjetura en la que se basó el algoritmo para resolver GI en el tiempo polinomial. A saber:
que los gráficos representativos exhiben la división de automorfismo del gráfico dado
Obviamente, esta conjetura no está probada hasta ahora (de lo contrario, sabríamos que GI está en P). Mi pregunta es si ya se demostró que era falso y, posiblemente, ¿se dio un contraejemplo?
fuente