Ustalony punkt łączymy trzema krawędziami z trzema rozłącznymi egzemplarzami
grafu \(\displaystyle{ K _{7}}\).
a) Ile drzew spinających ma otrzymany graf?
b) Ile jego krawędzi zawiera każde drzewo spinające tego grafu?
a) Z tw. Cayleya: graf pełny \(\displaystyle{ K _{n}}\) ma \(\displaystyle{ n ^{n-2}}\) drzew spinających.
Dodatkowo dla grafu będącego złączeniem dwóch grafów pełnych \(\displaystyle{ K _{n}, K _{m}}\) połączonych krawędzią zachodzi: \(\displaystyle{ n ^{n-2} \cdot m ^{m-2}}\) - ilość drzew spinających. Czyli dla dwóch grafów \(\displaystyle{ K _{7}}\) złączonych dodatkową krawędzią jest \(\displaystyle{ 7 ^{10}}\) drzew spinających. Dla trzech grafów można postąpić tak samo. Jednak różni się takie połączenie od tego w treści zadania.
b) Każde drzewo ma \(\displaystyle{ n - 1 }\) krawędzi, gdzie n to liczba wierzchołków. Wtedy liczba wszystkich krawędzi w grafie to: \(\displaystyle{ {n -1 \choose 2}}\).
Jak podejść do tego zadania w przypadku gdy jest dodatkowy wierzchołek i 3 grafy pełne połączone są poprzez nowy wierzchołek? Jak wykorzystać informacje które podałem? Proszę o pomoc w rozwiązaniu.