Witam.
Mam takie zadanie: ile jest drzew spinających nie mających wierzchołka stopnia 4 grafu pełnego mającego 9 wierzchołków?
Jeśli trzeba policzyć wszystkie drzewa to mogę użyć wzoru Cayleya, czyli \(\displaystyle{ n^{n-2}}\) (co daje \(\displaystyle{ 9^7}\)). Jak jednak policzyć liczbę drzew z \(\displaystyle{ \mbox{deg}(v)=4}\), aby móc odjąć je od wszystkich drzew?