Teoria grafów - izomorfizm drakerc: Sprawdź poprawność zdania: Wszystkie grafy proste o 8 wierzchołkach i 25 krawędziach są izomorficzne Jak to sprawdzić? Jaka będzie odpowiedź? Przez sprawdzenie dopełnienia do grafu pełnego?

drakerc: czy w ogóle jest to możliwe, by graf o 8 wierzchołkach miał 25 krawędzi?

g: Graf pełny o 8 wierzchołkach ma 28 krawędzi. Jeśli graf ma 25, to znaczy że 3 usunięto. Usuwać można na różne sposoby: wychodzące z tego samego lub z różnych wierzchołków. Dlatego nie wszystkie są izomorficzne, ale pewne podgrupy można znaleźć w których będzie izomorfizm.

drakerc: Rozumiem. Czy żeby to udowodnić, to najprościej byłoby narysować dwa grafy dopełnień o 8 wierzchołkach, 3 krawędziach, które łączą różne wierzchołki i stwierdzić, że dopełnienia nie są izomorficzne, to i grafy nie są? I jeszcze jedno: czy wszystkie grafy o 8 wierzchołkach i 28 krawędziach są izomorficzne? Byłby to graf pełny, a chyba one z założenia zawsze są izomorficzne, prawda?