Feladat: 9.7.
* Egy
n pontú egyszerű gráfban a független élek maximális száma
k. Bizonyítsuk be, hogy ha
n≥2k+2, akkor a gráfnak legfeljebb
kn-k éle van.
Mi a helyzet
n=2k+1 pont esetén?
Megjegyzés. Ez a becslés
k=1-re pontos, de
k>1-re nem az. A maximális élszám kicsit kevesebb, mint
kn-k. A különbség azonban már nem függ
n-től, csak
k-tól. Az élszám pontos felső korlátjának bizonyítása azonban általában körülményes, ezért csak a legegyszerűbb
k=2 esetben adjuk majd fel a
9.9. feladatban.
Megoldás: 9.7
Legyen
x1
y1
,…,
xk
yk
egy maximális független élrendszer a gráfban. A gráf többi pontjának halmazát jelöljük
T-vel.
T pontjai között nem futhat él. Meg akarjuk becsülni, hány él indulhat az
xi
és
yi
pontokból
T-be. Ha
xi
-ből megy él egy
uεT pontba, akkor a párjából,
yi
-ből nem futhat él
T-nek
u-tól különböző pontjába. Ha ugyanis futna él egy
vεT pontba, akkor az
xi
yi
élet kicserélhetnénk az
xi
u,
yi
v élpárra és nagyobb független élrendszert kapnánk, ami ellentmond feltevésünknek.
Ebből viszont következik, hogy vagy
u van összekötve
xi
-vel és
yi
-vel és
T többi pontja közülük egyikkel sem, vagy
yi
nincs összekötve
T egyetlen pontjával sem. Mindkét esetben legfeljebb
n-2k él fut az
xi
yi
végpontjaiból
T-be. Ezt az összes
xi
yi
élre összeadva azt kapjuk, hogy a független élek végpontjaiból
T-be legfeljebb
k(n-2k) él fut. Másrészt a független élek végpontjai között legfeljebb
k(2k-1) él fut. Ez összesen legfeljebb
kn-k él, ahogy a feladat állítja. (Érdemes meggondolni, hol használtuk, hogy
n≥2k+2.
Ha
n=2k+1, akkor a teljes gráfban sincs
k+1 független él, tehát a maximális élszám
k(2k+1).