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.
Megoldás: 2.10
Jelöljük egyelőre
f(n)-nel a minimális élszámot, és próbáljuk alkalmazni a
2.8.) feladat gondolatmenetét. Ha
n=2k+1 vagy
=2k+2, akkor van egy legalább
k-adfokú pont (lásd az előző,
2.9. feladatot). Ezt elhagyva a maradó gráfban van legalább
f(n-1) él. Azt kapjuk tehát, hogy
f(2k+1)≤k+f(2k),
f(2k+2)≤k+f(2k+1).
|
Az utóbbiba az előbbit beírva azt kapjuk, hogy
f(2k+2)=2k)+f(2k). Ha ezt folytatjuk, akkor végül arra jutunk, hogy
f(2k+2)≤2(k+1)+2k+…+4+f(2)=2(1+2+3+4+…+k)=k(k+1).
|
| () |
Ha a gráf két darab pontdiszjunkt
k+1 pontú teljes gráf uniója, akkor pontosan
k(k+1) éle van, tehát
f(2k+2)=k(k+1), vagy ami ugyanaz
f(2k)=k(k-1).
Ugyanígy kiszámolható, hogy
f(2k+1)≤
k2
, és egy-egy pontdiszjunkt
k pontú és
k+1 pontú teljes gráf uniójának pontosan
k2
éle van és nincs benne pontfüggetlen hármas. Tehát
f(2k+1)=
k2
.
Ezzel ismét bebizonyítottuk Turán tételét, most a következő formában:
Turán-tétel. Ha egy
n pontú egyszerű gráfban nincs három független pont (azaz bármely három pontja közül valamely kettő között fut él), akkor
ha
n=2k páros, akkor legalább
k2
-k éle van,
ha
n=2k+1 páratlan, akkor legalább
k2
éle van.
Mint említettük (
2.6. feladat), ez csak megfogalmazásában különbözik a
2.3. feladatban kimondott Turán-tételtől: itt a komplementer gráfra fogalmaztuk át az állítást. A tételre több bizonyítást is adunk. Az itt adott két bizonyításon kívül lásd még a
6.1. feladat megoldását és a
K.II.12.17. feladat megoldását.
A bizonyítást nyomon követve az is kijön, hogy a megadott két példa az egyetlen példa
f(n) pontú gráfra, amelyben nincs független hármas. A tételre adandó többi bizonyításból ez a többlet hamarabb megkapható. Ezt már korábban bebizonyítottuk, itt nem bíbelődünk vele.