Falls ein Graph mit n Knoten weniger als n-1 Kanten hat, dann kann er nicht zusammenhängend sein. Begründung?

Question

Falls ein Graph mit n Knoten weniger als n-1 Kanten hat, dann kann er nicht zusammenhängend sein. Begründen Sie diese Aussage, mit Beweis.

Answer 1

Beweis über vollständige Induktion (Wichtig - eine Kante verbindet immer genau zwei Knoten.):

Induktionsanfang: \(n=2\) Ein Graph mit 2 Knoten und keiner Kante hängt offensichtlich nicht zusammen

Induktionsschritt von \(n\) nach \(n+1\): Liegt ein Graph mit \(n\) Knoten vor und weniger als \(n-1\) Kanten vor, so hängt er nicht zusammen. Es existieren also mindestens zwei isolierte zusammenhängende Graphen. Durch Hinzufügen eines weiteren Knotens und einer weiteren Kante kann man jetzt entweder den neuen Knoten mit einem der beiden Graphen oder die beiden Graphen miteinander verbinden. Aber nicht beides - d.h. es liegt am Ende wieder ein nicht zusammen hängender Graph vor.

q.e.d.

Answer 2

Jeder Graph mit zwei Knoten und weniger als einer Kante besteht aus mindestens zwei Zusammenhangskomponenten.

Wenn jeder Graph mit n Knoten und weniger als n-1 Kanten aus mindestens zwei Zusammenhangskomponenten besteht, dann besteht jeder Graph mit n+1 Knoten und weniger als n-1 Kanten aus mindestens drei Zusammenhangskomponenten, weil ein Knoten aber keine Kante hinzugekommen ist. Durch Hinzufügen einer Kante können zwei dieser Zusammenhangskomponenten zu einer zusammengefügt werden. Also besteht jeder Graph mit n+1 Knoten und weniger als (n+1)-1 Kanten aus mindestens zwei Zusammenhangskomponenten.