Megoldás: 2.12
Jelöljük
f(n)-nel a keresett minimális élszámot.
A
2.11. feladat a) részéből tudjuk, hogy ha
n>3k, és
G olyan
n pontú gráf, amelyben nincs független pontnégyes, akkor
G-ben van egy legalább
k-adfokú pont. Ha egy ilyen pontot a belőle induló élekkel együtt elhagyunk a gráfból, akkor továbbra sem lesz benne független pontnégyes, ezért tudjuk, hogy legfeljebb
f(n-1) éle van. Ebből azt kapjuk, hogy
f(3k+1)≤k+f(3k),
f(3k+2)≤k+f(3k+1),
f(3k+3)≤k+f(3k+2).
|
Innen a három egyenlet összeadása után az jön ki, hogy
Ha ezt
k=1,2,…,n-1-re összeadjuk, és tekintetbe vesszük, hogy
f(3)=0, akkor azt kapjuk, hogy
f(3n)≤3n(n-1)/2.
Másrészt az a
3n pontú gráf, amely három, páronként pontdiszjunkt
n pontú teljes gráfból áll, pontosan
3n(n-1)/2 élű és nincs benne független pontnégyes. Tehát
f(3n)=3n(n-1)/2. (Ez a teljes gráf éleinek mintegy harmada.)
Hasonlóan kapjuk a fenti egyenletekből (most az utolsó helyett
f(3k)-ra kell felírni az egyenletet és úgy összeadni a hármat), hogy
f(3k+2)-f(3k-1)≤3k-1, s ezt
k=1,2,…,n-1-re összeadva azt kapjuk, hogy
f(3n-1)≤3n(n-1)/2-(n-1)=(3n-2)(n-1)/2.
|
Az a gráf, amely két darab
n pontú teljes gráf és egy
n-1 pontú teljes gráf pontdiszjunkt uniója, pontosan ennyi élből áll, és nincs benne független pontnégyes. Tehát
f(3n-1)=(3n-2)(n-1)/2.
Végül ugyanígy jön ki az is, hogy
f(3k+1)-f(3k-2)≤3k-2, s ezt ismét
k=1,2,…,n-1-re összeadva
f(3n-2)≤3n(n-1)/2-2(n-1)=(3n-4)(n-1)/2. Az a gráf, amely egy
n pontú és két
n-1 pontú teljes gráf pontdiszjunkt uniója, pontosan ennyi élű és nincs benne független pontnégyes. Tehát
f(3n-2)=(3n-4)(n-1)/2.
A minimális élszámot tehát mindig úgy kapjuk, ha vesszük azt az ,,extrém gráfo", amit úgy kapunk, hogy az
n pontot beosztjuk lehetőleg egyenletesen három csoportba és az egy csoportban levőket összekötjük. (Tehát három olyan teljes gráf pontdiszjunkt unióját vesszük, ahol a teljes gráfok pontszáma között legfeljebb egy a különbség.)
Megjegyzés. Nem okoz ezután meglepetést, hogy az ugyanezzel a gondolatmenettel a
2.11. feladat b) részéből megkaphatjuk azt is, hogy minimálisan hány éle van egy olyan
n pontú gráfnak, amelyben nincs
k független pont. A válasz: a minimumot a következő gráf szolgáltatja: az
n pontot felosztjuk a lehető legegyenletesebben
k-1 csoportra (azaz úgy, hogy bármely két csoport elemszáma között legfeljebb egy legyen a különbség), és minden csoport pontjai egy-egy teljes gráfot feszítenek.