Megoldás: 2.18
k-ra vonatkozó teljes indukcióval bizonyítunk, éspedig
k-2-ról
k-ra. Ehhez bevonjuk a
k=1 és
k=2 eseteket is. Szerencsére a
k=1 eset semmitmondóan igaz: kétpontú és legalább kétélű egyszerű gráf ugyanis nincsen, így nem kell semmit bizonyítani. Viszont
k=2 esetén nem igaz a feladat állítása, hiszen a négypontú teljes gráfnak hat éle van és nincs benne
C5
. Az indukciós lépést tehát
k>2-re fogjuk bizonyítani, de a
k=4 esetben figyelni kell arra, hogy csak gyengébb feltételt tudunk. A továbbiakban tehát
k>2 és feltesszük, hogy
k-2-re már
k=2 eset kivételével tudjuk az állítást, és az
n=2k pontú,
k2
+1 élű gráfra akarjuk bebizonyítani, hogy van benne
C5
.
Első lépésként megelégszünk kevesebbel: az
1.5. feladat szerint minden
n=2k pontú,
k2
+1 élű gráfban van
C4
. Legyenek ennek pontjai az
1,2,3,4 számokkal jelölve úgy, hogy az
12,
23,
34,
41 élek a gráfban vannak. Jelölje a gráf többi pontjának halmazát
T.
T elemszáma
2(k-2). Tehát ha
T-ben legalább
(k-2
)2
+1 él fut, akkor az indukciós feltevés szerint van benne
C5
. A továbbiakban tehát feltehetjük, hogy
T-ben legfeljebb
(k-2
)2
él van. Ekkor legalább
4k-3 él van, amelynek egyik végpontja az
1234 kör valamelyik pontja.
(Külön kell vizsgálnunk a
k=4 esetet. Ekkor
T-ben négy pont van. Ha közöttük is legfeljebb négy él fut, akkor itt is
4k-3=13 él marad, amelynek egyik végpontja az
1234 kör valamelyik pontja. ,,Baj" tehát csak akkor van, ha
T-ben öt vagy hat él fut. De ekkor választhatjuk ezt a négy pontot
1234-nek és még azt is tudjuk, hogy a körnek legalább egy átlója van.)
Ha valamely
uεT össze van kötve e kör két szomszédos pontjával, akkor máris találtunk egy
C5
-öt. Tehát feltehetjük a továbbiakban, hogy
T minden pontja a kör legfeljebb két pontjával van összekötve. Ez legfeljebb
4(k-2) él. A kör négy pontja között tehát legalább öt él fut. Feltehetjük, hogy az
13 él be van húzva. Ez azt jelenti, hogy ha
T valamely
u pontja
2-vel és
4-gyel is össze van kötve, akkor
u2134u egy
C5
-öt alkot. Ha a
24 él is be van húzva, akkor ugyanez a helyzet, ha
u az
1 és
3 pontokkal van összekötve. Mivel azt már kizártuk, hogy szomszédos pontokkal legyen összekötve, ebben az esetben azt kapjuk, hogy
T minden pontja körünk legfeljebb egy pontjával van összekötve, ami összesen legfeljebb
2k-4 él. Ez a kör pontjai között futó hat éllel is legfeljebb
2k+2<4k-3 él, ami ellentmondás.
(Itt megint külön kell vizsgálnunk a
k=4 esetet. Azt kaptuk, hogy a gráfnak legfeljebb
2k+2 éle, plusz a
T négy pontja között futó legfeljebb hat éle van, ami még mindig csak 16 él a feltételezett 17 helyett. Ez is ellentmondás.)
Marad az az eset, ha
24 nem él a gráfban, tehát a kör négy pontja között öt él fut. Ekkor a kör és
T pontjai között legalább
4k-3-5=4(k-2) él fut. Láttuk már, hogy ez csak úgy lehetséges, ha minden pont az
1 és
3 pontokkal van összekötve. Legyen most
T két éllel összekötött pontja
u és
v. Most például az
u143vu egy
C5
-öt alkot. Ha viszont
T pontjai között egyáltalán nem futna él, akkor a gráfban összesen
4k-3<
k2
+1 él van, ami ellentmondás. (Itt a
k=4 esetet nem kellett külön vizsgálnunk.)
Van olyan
2k pontú,
k2
élű gráf, amelyben nincs
C5
: a
Kk,k
teljes páros gráf. Vagyis
e5
(2k)=
e3
(2k) és az extrém gráf is megegyezik. (Bebizonyítható, hogy más extrém gráf
C5
esetében sincs.)
Ezzel a bizonyítást befejeztük annak bizonyítását, hogy
e5
(2k)=
k2
.