TU Wien:Diskrete Mathematik für Informatik UE (Gittenberger)/Übungen WS13/Beispiel 13

13) If T is a tree having no vertex of degree 2, then T has more leaves than internal nodes. Prove this claim

• a) by induction,
• b) by considering the average degree and using the handshaking lemma.

Solution

d...degree
v...Vertex
B...Blatt
I...Interner Knoten

interner Knoten (I) : d(v)>1
Blatt (B) : d<=1

Induktion:
n=1: o (B=1, I=0, ok) n=2: o--o (B=2, I=0, ok) usw.

n=k: 2 Fälle:

• a. wir verbinden einen neuen Knoten (der immer ein Blatt ist!) mit einem internen Knoten: |I| bleibt gleich, |B| wird um eins erhöht (ok)
• b. wir verbinden einen neuen Knoten mit einem Blatt: Das bisherige Blatt hat nun d(v)=2, das ist aber laut Aufgabe nicht erlaubt. Also kann der Fall nicht eintreten.

Man sieht also, dass stets |B| > |I| gilt

Kommentar:

Ich widerspreche. Dies gilt nur, wenn man zeigen kann, dass auf diese Art und weise jeder Baum ohne Knotengrad 2 der Größe k aus einem Baum ohne Knotengrad 2 der Größe k-1 durch Hinzufügen eines Blattes konstruiert werden kann. Dem ist nicht der Fall. Hier ein Gegenbeispiel:

---o---

--/|\--

-o-o-o-

--/-\--

-o---o-

Durch Entfernen eines Blattes hat dieser Graph wieder Knotengrad 2 und kann daher nicht durch die obrige Regel konstruhiert werden. --21:19, 19. Okt. 2017 (CEST)

über Handshaking Lemma:
Summe d(v) >= 3*|I| + |B|
Sowie über Handshaking Lemma und Tree Vertex Edge Formel: Summe d(v) = 2 * |E| = 2 * (|V|-1) = 2 * (|I|+|B|-1)
entsprechend umformen, und schon sieht man, dass |B|>|I| gilt.
Da ja der durchschnittliche Degree gefragt ist, kann man natürlich noch durch die Summe der Degrees dividieren - allerdings ändert das nichts da es sich wegkürzt.