Zadania z grafów Hamilton: 1. Ile drzew spinających ma graf K₇, jeśli łączymy go z cyklem C₉ jedną wspólną krawędzią? Jest jakiś warunek dla łączenia K_n z C_m wspólną krawędzią albo wierzchołkiem? Gdy łączymy C_n i C_m wspólną krawędzia to ma m*n−1 drzew spinających, jak K_n i K_m to chyba m^m−2*nⁿ⁻²? W tym przypadku jest jak? 2. Do grafu K₉ dodajemy krawędź. Jaką liczbe i indeks chromatyczny ma otrzymany graf? Liczba chromatyczna ϰ(K_n) = n więc dla K₉ wynosi 9, a indeks ϰ'(K_n) = n dla n nieparzystych więc też 9. A co jak dodamy tą krawędź?

Hamilton: Jeszcze jedno zadanie: 3. Do grafu, który jest eulerowski, niehamiltonowski, nieplanarny dodajemy krawędź. Jaki będzie otrzymany graf?

jc: 1. 9*7⁵ 2. 9, 9

Hamilton: To w drugim dodatkowa krawędź nic nie zmienia?

jc: Do pomalowania K_n na pewno wystarczy n kolorów. Z każdego wierzchołka wychodzi n−1 krawędzi. Jak dodasz n krawędź, to możesz ją pomalować na kolor, który wśród tych n−1 nie występuje.