Wierzchołkami grafu \(\displaystyle{ K_{7}}\) są \(\displaystyle{ 1,2,...,7}\), a kolejnymi wierzchołkami cyklu \(\displaystyle{ C_{5}}\) są \(\displaystyle{ 8,9,...,12}\). Wierzchołek 7 łączymy krawędzią z wierzchołkiem 12.
a) ile drzew spinających ma otrzymany graf?
b) ile spośród drzew spinających tego grafu nie zawiera krawędzi 8-9 ?
Rysujemy, wiemy, że graf \(\displaystyle{ K_{7}}\) ma \(\displaystyle{ 7^{5}}\) drzew spinających (wzór na ilość drzew spinających grafu pełnego), a cykl \(\displaystyle{ C_{5}}\) ma ich \(\displaystyle{ 5}\). Są połączone krawędzią, zatem odpowiedź do podpunktu a: \(\displaystyle{ 7^{5} \cdot 5.}\)
Jak zrobić podpunkt b? Wiem, że jeśli byłoby pytanie "ile spośród drzew spin. nie zawiera krawędzi np. 11-12", to odpowiedź byłaby bez tej piątki, czyli \(\displaystyle{ 7^{5}}\). A jak jest w tym przypadku, będzie tak samo, czy jest jakaś różnica?
Z góry dzięki za pomoc.