Direkt zum Inhalt

Lexikon der Mathematik: Turán, graphentheoretischer Satz von

sagt aus, daß für r, n ≥ 2 der Graph Tr(n) der eindeutige kantenmaximale Graph der Ordnung n ist, der keinen vollständigen Graphen Kr+1 der Ordnung r + 1 als Teilgraphen enhält.

Dabei ist der sogenannte Turansche Graph Tr(n) der vollständige r-partite Graph, dessen Partitionsmengen für 1 ≤ ir jeweils die Kardinalität \(\lfloor \frac{n+i-1}{r}\rfloor \) haben.

Turán bewies diesen Satz 1941. Man erkennt leicht, daß der Tr(n) mindestens \(\left(1-\frac{1}{r}\right)\binom{n}{2}\) Kanten enthält. Ein Graph der Ordnung n mit mehr Kanten als Tr(n) enthält also zwangsläufig einen Kr+1 als Teilgraphen.

Der Satz von Erdos-Stone (Erdos-Stone, Satz von) verschärft diese letzte Aussage wesentlich.

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