Wie viele Kanten muss ein Graph G der Ordnung n haben, damit er jedenfalls zusammenhängend ist?

Question

Wobei G der Name des Graphens ist und n die Anzahl an Knoten (edges) des Graphens. Ich bin auf (n-1) gekommen, diese Überlegung kommt mir jedoch etwas einfach vor.

Comments

War das so ähnlich wie hier gemeint ?

https://www.mathelounge.de/312669/ich-muss-zeigen-dass-ein-graph-g-zusammenhangend-ist

Answer 1

Nimm mal n = 6 Knoten und verbinde diese zu zwei Dreiecken. Dann hast du n = 6 Kanten aber trotzdem nichts zusammenhängendes. Meinst du das in der Art?