Hallo,
Nach dem Handshake Lemma ist bei einem Graphen \(G(V,E)\) die Summe aller Grade aller Knoten \(v \in V\) gleich dem Doppelten der Anzahl \(|E|\) der Kanten$$\sum_{v \in V} \deg(v) = 2|E|$$Sie \(n_4\) die Anzahl der Knoten mit Grad 4 und \(n_5\) die Anzahl der Knoten mit Grad 5, so ist die Summe der Grade$$\sum_{v \in V} \deg(v) = 14 + 4n_4 + 5n_5$$wegen der 14 Blätter, die zwangsläufig vom Grad 1 sind.
Die Anzahl der Kanten \(|E|\) ist bei einem Baum die Anzahl der Knoten minus 1. Also in diesem Fall$$|E| = 14 + n_4 + n_5 -1 $$Beide Informationen in die Gleichung für das Handshake Lemma ensetzen gibt$$\begin{aligned} 14 + 4n_4 + 5n_5&= 2(14 + n_4 + n_5 -1) \\ 2n_4 + 3n_5 &= 12\end{aligned}$$Und natürlich sind \(n_4,\,n_5 \in \mathbb N_0\); weiter kann \(n_5\) nur eine gerade Zahl sein. Also gibt es genau die drei Möglichkeiten$$(n_4,\,n_5) \in \{(6,\,0), \space (3,\,2), \space (0,\, 4)\}$$Gruß Werner
