Baum mit einem Knoten vom grad k besitzt mindestens k Blätter.

Question

Ich stehe leider bei folgender Frage an:

Baum mit einem Knoten vom grad k besitzt mindestens k Blätter hat.

Ich weiß, dass ein Baum mit n Knoten (n-1) Kanten hat. Nun habe ich einen Baum mit einem Knoten von grad k, dh ja dass ich mind. (k+1) Knoten im Baum habe oder? d.h. mindestens k Kanten und somit gilt dann ∑deg(v) ≤ 2*k ≤ 2(n-1) oder?

nun weiß man, dass ein nicht trivialer Baum mind. 2 Blätter hat --> ∑deg(v) = 1 + 1 + k + ....... weiter weiß ich leider nicht mehr.

Answer 1

Der Wald, den man bekommt indem man den Knoten vom Grad k und dessen inzidente Kanten entfernt, besteht aus k Zusammenhangskomponenten. Jede Zusammenhangskomponennte ist selbst wiederum ein Baum und hat mindestens ein Blatt.

Besteht die Zusammenhngskomponente aus nur einem Knoten, dann war der noten Blatt des ursprünglichen Bauems. Besteht die Zusammenhngskomponente aus mehreren Knoten, dann hat die mindestens ein zweite Blatt. Dieses Blatt war auch Blatt des ursprünglichen Baumes.