Turánova věta

Turánova věta je pojem z teorie grafů. Popisuje, jak by měl vypadat graf, který má mít co nejvíce hran, a přesto nemá obsahovat úplný graf Kn-1 jako svůj podgraf. Je pojmenována podle Pála Turána.

Podle Turánovy věty by takový graf měl být n-partitní. Přidáním jakékoli další hrany do n-partitního grafu v něm již někde vznikne daný nechtěný úplný podgraf Kn-1.

Reference

Kategorie:Teorie grafů