Graphentheorie: Zeige: Ein Baum mit mindestens zwei Knoten hat immer mindestens zwei Blätter

Question

Aufgabe

Beweise, dass ein Baum mit mindestens zwei Knote(n immer mindestens zwei Blätter hat.

Problem/Ansatz:

Ich weiß gar nicht, wie man das beweisen soll, ich habe ans Handshaking Lemma gedacht, weiß jedoch nicht wie ich das damit beweisen soll.

Comments

Tipp: Beginne mit der Definition von Baum. Dann auch die Definition von Blatt angeben.

https://www.mathelounge.de/444111/baum-mit-einem-knoten-vom-grad-k-besitzt-mindestens-blatter ist etwas komplizierter. Wenn du keine Angst davor hast, lies das ruhig mal. 

---

Danke für die Antwort. Die Definition vom Baum habe ich im Kopf, weiß jedoch nicht wie ich damit arbeiten kann. Ein Baum ist ein zusammenhängender , zyklenfreier Graph. Wobei zyklenfrei bedeutet, dass jeder Knoten durch genau einen Weg verbunden ist, also nur genau je eine Hin und je eine Rückkante pro Knoten existiert. Zusammenhängend bedeutet, dass jeder Teilgraph T1 des Graphen T durch eine Kante verbunden ist, also ein Weg existiert. Wie kann ich damit dann die Lösung finden ? Den Post habe ich leider nicht verstanden, ist etwas zu allgemein definiert. ICh würde mich über eine Antwort freuen! Schönes Wochenende!

Answer 1

Ein Ansatz wäre, die Aussage über Induktion zu zeigen, indem du die Induktion über die Anzahl an n:=|V|≥2 Knoten vom Baum führst. Ein Blatt ist ja ein derartiger Knoten, welcher keine Kindknoten hat, also Knotengrad 1 besitzt.

Answer 2

Hallo,

vielleicht noch ein alternativer Beweisvorschlag: Betracht im Baum einen längsten Weg (also einen Weg mit der Maximalzahl an Kanten). Zeige, dass die beiden Endknoten Blätter sind.

Gruß