TU Wien:Diskrete Mathematik für Informatik VU (Drmota)/Übungen WS20/Beispiel 11

Let T be a tree and let $n_{d}$ be the number of vertices of degree d in T. Show that the number of leaves of T equals $2+\sum _{d>=3}(d-2)n_{d}$

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Hilfreiches

• Handshaking lemma

Lösungsvorschlag

Let l be the number of leaves, n = |V| the number of vertices and L the set of leaves.
Using the handshaking lemma we have
$2*|E|=\sum _{v\in V}d(v)$
$2*(n-1)=\sum _{v\in V}d(v)$
Each leaf node has a degree of 1, so we have l nodes with a degree of 1
$2*(n-1)=l+\sum _{v\in V\setminus \{L\}}d(v)$
Every vertex in V - L has at least degree of 2
$2*(n-1)=l+2*(n-l)+\sum _{v\in V\setminus \{L\}}d(v)-2$
$2n-2=l+2n-2l+\sum _{v\in V\setminus \{L\}}d(v)-2$
$2n-2=2n-l+\sum _{v\in V\setminus \{L\}}d(v)-2$
$l=2+\sum _{v\in V\setminus \{L\}}d(v)-2$
For $v\in V\setminus L$ and d(v) = 2, the summand is 0.
$l=2+\sum _{d>=3}(d(v)-2)n_{d}$