Jak udowodnić izomorficzność grafów?

[uczen23]

Udowodnić, że wszystkie grafy proste, o sześciu wierzchołkach, których każdy wierzchołek jest stopnia \(\displaystyle{ 4}\), są izomorficzne.

[Mruczek]

Popatrzmy na dopełnienia tych grafów. W dopełnieniu każdy wierzchołek ma stopień \(\displaystyle{ 1}\), a to znaczy, że dopełnienie to trzy krawędzie. Dlatego dopełnienia każdego z tych grafów są izomorficzne, więc i początkowe grafy też.

[uczen23]

skąd wiadomo, że jeśli dopełnienia grafów są izomorficzne, to początkowe grafy też?

[Mruczek]

No bo jeżeli mamy izomorficzność dwóch grafów to znaczy że istnieje bijekcja \(\displaystyle{ f}\) taka, która przekształca zbiór wierzchołków pierwszego grafu na zbiór wierzchołków drugiego grafu tak, że wierzchołki \(\displaystyle{ x, y}\) pierwszego grafu są połączone krawędzią w pierwszym grafie, wtedy i tylko wtedy gdy, \(\displaystyle{ f(x), f(y)}\) są połączone krawędzią w drugim grafie. No a biorąc dopełnienie, jeżeli były połączone w pierwszym grafie to w jego dopełnieniu nie są (i na odwrót) i to samo z drugim grafem, czyli powyższy warunek nadal jest spełniony.

[uczen23]

i za każdym razem to działa? że jeśli dopełnienia się izomorficzne, to podstawowe grafy też?

[Mruczek]

Działa, bo podstawowy graf jest dopełnieniem dopełnienia tego podstawowego grafu.