Ich muss zeigen, dass ein Graph G zusammenhängend ist.

Question

Es sei G ein Graph mit n Knoten und q Kanten. Ich soll zeigen, dass G zusammenhängend ist, wenn $$ q\quad >\quad \left( \begin{matrix} n-1 \\ 2 \end{matrix} \right)  $$ ist.

Ich bin für jeden Gedanken zu einem Lösungsvorschlag dankbar!

Comments

Sieht nach vollständiger Induktion aus.

---

Und wie genau? Ich meine, ich habe schon oft Beispiele durch vollständige Induktion bewiesen, aber hier stehe ich völlig auf der Leitung.

Was ist meine Induktionsbasis?

Answer 1

Annahme: Kanten verbinden jeweils zwei unterscheidbare Knoten. Und zwischen zwei verschiedenen Knoten gibt es maximal eine Kante.

Dann ist ((n-1) tief 2) die maximale Anzahl der Kanten in einer Menge von n-1 Knoten. Jede weitere Kante würde zwangsläufig zu einem n-ten Knoten führen.

D.h. mit nur ((n-1) tief 2) Kanten wäre es gerade noch möglich, dass n-1 der n Knoten nicht mit dem n-ten Knoten zusammenhängen.

Nun muss noch gezeigt werden, dass jede andere unzusammenhängende Aufteilung der n Knoten. Z.B. in n-4 und 4 Knoten weniger als ((n+1) tief 2) Kanten aufweisen kann.