W pracy „Efficient Al Algorytm for Graph Isomorphism” autorstwa Corneila i Gotlieba, 1970, stwierdzono hipotezę, na której opierał się algorytm rozwiązywania GI w czasie wielomianowym. Mianowicie:
że reprezentatywne wykresy wykazują podział automorfizmu na dany wykres
Oczywiście, ta hipoteza nie została do tej pory udowodniona (w przeciwnym razie wiedzielibyśmy, że GI jest w P). Moje pytanie brzmi, czy zostało już udowodnione, że jest fałszywe i czy może podano przeciwny przykład?
źródło