Wie beweise ich mit Induktion, dass ein Baum mit n Knoten, mindestens n-1 Kanten besitzt?

Question

Ich weiß nicht wie ich das mit Induktion beweisen soll:

Ein Baum mit n Knoten hat mindestens n-1 Kanten.

Für den Induktionsanfang habe ich n=1 -> Ein Baum mit einem Knoten hat 1-1=0 Kanten. Das stimmt ja so. Aber ich weiß nicht wie ich sinnvoll weiter machen soll... da man ja eigentlich n+1 als Induktionsschritt nehmen müsste und das ja mit dem n-1 nen bisschen in die quere kommt. Ich bin total verwirrt. :-(

Answer 1

Die Verankerung hast du ja schon selbst gemacht. Hier nur:

Induktionsschritt n---> n+1

Induktionsvoraussetzung: Ein Baum mit n Knoten hat n-1 Kanten.

Induktionsbehauptung: Ein Baum mit n+1 Knoten hat n Kanten.

Beweis:

Ein Baum mit n+1 Knoten ist ein Baum mit n Knoten, an den ein Knote angebaut wird.

Dazu braucht es eine Kante.

Nach Induktionsvoraussetzung besitzt der Baum schon n-1 Kanten. Der neue hat eine Kante mehr. Also (n-1) + 1 = n Kanten. qed Induktionsschritt.