Grapheigenschaft. Beweisen Sie, dass mindestens eine Zusammenhangskomponente ein Baum ist.

Question

Aufgabe:

Sei G ein einfacher, ungerichteter, nicht zusammenhängter Graph mit n Knoten und m=n-1 Kanten.

Beweisen Sie, dass mindestens eine Zusammenhangskomponente ein Baum ist.

Answer 1

Ein Kreis aus \(k\) Knoten hat \(k\) Kanten.

Ist jede Zusammenhangskomponente von \(G\) ein Kreis, dann benötigt man \(n\) Kanten.

Ist in einer Zusammenhangskomponente mit \(k\) Knoten ein Kreis mit \(p < k\) Kanten, dann benötigt man mindestens \(k-p\) Kanten um die nicht auf dem Kreis liegenden \(k-p\) Knoten mit der Zusammenhangskomponente zu verbinden. Die Zusammenhangskomponente hat also mindestens \(p + (k-p) = k\) Kanten.