Feladat: 2.13.
Maximálisan hány éle lehet egy olyan
n pontú egyszerű gráfnak, amelyben nincs
k pontú csillag (
n>k)?
Megoldás: 2.13
A kérdés egyenértékű azzal, hogy maximálisan hány éle lehet egy olyan gráfnak, amelyben minden pont foka legfeljebb
k-2. Ha
k páros, akkor minden
n-re van
n pontú,
k-reguláris egyszerű gráf (l. a
2.7. feladatot), tehát a maximális élszám
n(k-2)/2. Ha
k páratlan akkor minden páros
n-re van ilyen reguláris gráf, tehát a maximális élszám most is
n(k-2)/2. Marad az az eset, ha
n is,
k is páratlan. Ekkor vegyük a
2.7. feladatban definiált
n-1 pontú,
k-2-reguláris gráfot. Hagyjuk el az
12,34,…,(k-4)(k-3) éleket és kössük össze az
1,2,…,(k-3) pontokat egy
n-edik ponttal. Így egy olyan gráfot kapunk, amelynek
n-1 pontja (ez utolsó pont kivételével minden pontja)
k-2-edfokú, az
n-edik pont pedig
k-3-adfokú. Nyilván ez a maximális élszám:
(n-1)(k-2)/2+(k-3)/2=⌊n(k-2)/2⌋.