Direkt zum Inhalt

Lexikon der Mathematik: dreiecksfreier Graph

ein Graph, der keinen vollständigen Graphen K3 der Ordnung 3 – also ein „Dreieck“ – als Teilgraphen enthält.

Als Spezialfall des Satzes von Turán ergibt sich, daß ein dreiecksfreier Graph G der Ordnung n höchstens \(\lfloor \frac{{n}^{2}}{4}\rfloor \) Kanten besitzt.

Hat G tatsächlich die maximale Anzhal von \(\lfloor \frac{{n}^{2}}{4}\rfloor \) Kanten, dann ist G der vollständige bipartite Graph Kr,s mit \(r\,=\,\lfloor \frac{n}{2}\rfloor \) und \(s\,=\,\lfloor \frac{n}{2}\rfloor \).

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos