Feladat: 2.10.
Minimálisan hány éle lehet egy olyan
n pontú egyszerű gráfnak, amelyben nincs három független pont (azaz bármely három pontja közül legalább kettő között fut él)?
Megjegyzés. Turán Pál a tételét általánosabban is felállította. Általánosan az a kérdés, hogy legfeljebb hány éle van egy olyan gráfnak, amelyben nincs teljes
k-as (
k pontú teljes részgráf). Vagy a komplementerre átfogalmazva: legalább hány éle van egy olyan gráfnak, amelyben nincs
k független pont? Ez utóbbi kérdésre adnak választ a
2.11-
2.12. feladatok.