Graphentheorie: Vollständige Induktion

Question

Aufgabe:

Ein Dreieck in einem Graphen ist eine Teilmenge der Knotenmenge{a,b,c}⊆ V (G), für die alle drei Knoten paarweise adjazent sind, also gilt {a,b},{a,c},{b,c}∈ E(G). Beweisen Sie mit vollständiger Induktion, dass ein Graph mit 2n Knoten, der kein Dreieck als Teilgraphen enthält, höchstens n2 Kanten besitzt.

Problem/Ansatz:

Hatt jemand Ansätze um die Aufgabe zu lösen?

Answer 1

"Hatt jemand Ansätze um die Aufgabe zu lösen?"

Wie wäre es denn mit einem Induktionsanfang? Das ist der Ansatz für JEDEN Induktionsbeweis.

Auch wenn ich keine Ahnung von Graphentheorie habe: Ich bin der Meinung, dass die Aussage für n=1 falsch ist.

Zwischen 2*1=2 Knoten kann man kein Dreieck bilden, aber unendlich viele Kanten.

Comments

Im Sinne der Aufgabe kann man in einem (ungerichteten) Graphen genau eine Kante zwischen zwei Knoten bilden.

Der Induktionsanfang gilt für n=1, was offensichtlich sein sollte.