Vollständige Induktion: Zeige: Zusammenhängenden Graph mit mehr als einen Knoten hat mindestesn n-1 Kanten

Question

Aufgabe:

Jeder zusammenhängender Graph mit n Knoten (n>=2) hat mindestens n-1 Kanten

Problem/Ansatz:

tue mir da mit dem Inuktionschluss schwer. Nehmen wir an k = n - 1 Kanten. Beim Induktionschluss erhöhe ich für alle n : n+1.
Also k + n = n-1+1 <--> k + n = n

Dann Induktionsannahme einsetzen:

n- 1 + n = n <--> 2n -1 = n

Stimmt es etwa so? Falls ja wieso? Mir sagt das Ergebnis nichts

Comments

Vgl. auch https://www.mathelounge.de/30469/beweise-induktion-dass-baum-knoten-mindestens-kanten-besitzt (Gleiche Aufgabe)

Answer 1

IV: n Knoten => n-1 Kanten

IA: n = 2: der Graph ist zusammenhängend, also sind die zwei Knoten verbunden, du hast also 1 = 2 - 1 = n - 1 Kanten.

IS: n -> n + 1: du hast einen zusammenhängen Graphen mit n Knoten und n - 1 Kanten zwischen diesen Knoten. Jetzt kommt ein Knoten dazu und da der muss mit dem restlichen Graphen verbunden werden, da dein Graph n.V. zusammenhängend ist. Also kommt mindestens eine Kante dazu, jetzt hast du min. n - 1 + 1 = n = n + 1 - 1 Kanten.

q.e.d.