Kontrprzykład efektywnego algorytmu Corneila dla izomorfizmu grafów

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?

Mathon wykazał, że przypuszczenie zastosowane przez Corneila i Gotlieba jest fałszywe. Pierwsze odniesienie stwierdza ten fakt.

1- P. Foggia, C.Sansone, M. Vento, Porównanie wydajności pięciu algorytmów dla izomorfizmu grafów, Proc. Trzecie warsztaty IAPR-TC15 Reprezentacje oparte na grafach w rozpoznawaniu wzorów, 2001, s. 188–199.

2- R. Mathon, Przykładowe wykresy do badania izomorfizmu, Congressus Numerantium, 21, s. 499-517, 1978