Dalam makalah Suatu Algoritma Efisien untuk Grafik Isomorfisme oleh Corneil dan Gotlieb, 1970 sebuah dugaan dinyatakan di mana algoritma yang dinyatakan diandalkan untuk menyelesaikan GI dalam waktu polinomial. Yaitu:
bahwa grafik yang representatif menunjukkan partisi automorfisme dari grafik yang diberikan
Jelas, dugaan ini tidak terbukti sampai sekarang (kalau tidak kita akan tahu bahwa GI ada di P). Pertanyaan saya adalah apakah sudah terbukti salah dan mungkin contoh balasan diberikan?
sumber