Megoldás: 2.20
a) Az előző (
2.19.) feladat megoldásának jelöléseit és gondolatmenetét használjuk. Tehát legyen
x egy
d fokú pont, szomszédainak halmaza
Sx
(
|
Sx
|=d), az
x-szel össze nem kötött pontok halmaza
Nx
(
|
Nx
|=n-1-d). Láttuk, hogy az
Sx
által feszített részgráfban minden pont foka legfeljebb egy, tehát ebben a részgráfban legfeljebb
⌊d/2⌋ él van. Az
x-ből induló élek száma
d. Végül az
Nx
-et és
Sx
-et összekötő élek száma legfeljebb
n-1-d, ugyanis
Nx
minden pontjából csak egy él indulhat
Nx
-be. (Ha
y∈
Sx
össze van kötve
z,z'∈
Nx
-szel, akkor
yzxz'y egy
C4
.)
Ez összesen
d+⌊d/2⌋+n-1-d=n-1+⌊d/2⌋, ahogy állítottuk.
b) Legyen
G egy nyolcpontú, 12 élű egyszerű gráf. Ha van benne egy legfeljebb másodfokú pont, akkor hagyjuk ezt el a belőle induló élekkel együtt. Így egy hétpontú, legalább 10 élű gráfhoz jutunk, s arról a
3.18. feladat c) részéből már tudjuk, hogy van benne négy hosszú kör.
Marad az az eset, amikor minden pont foka legalább három. Mivel 12 él van, ez azt jelenti, hogy minden pont foka pontosan három.
Legyen
x egy pont,
Sx
a három szomszédjának a halmaza és
Nx
a négy ,,nem-szomszédjának" a halmaza. a) szerint az
Sx
pontjaiból induló élek száma legfeljebb nyolc. Így
Nx
-ben legalább négy élnek kell lennie. Ezek csak egyetlen esetben nem alkotnak egy négy hosszú kört: ha egyikük - legyen ez
z az összes többivel össze van kötve, és két szomszédja közt fut egy további él (l. a
3.18. feladatot). De akkor
z-nek már nem lehet több szomszédja, így belőle nem futhat él
Sx
-be. Vagyis legfeljebb három olyan él van, amely
Sx
-et és
Nx
-et köti össze, ami azt jelenti, hogy az
Sx
-ből induló élek száma legfeljebb
3+1+3=7. Ez viszont az
Nx
-beli legfeljebb négy éllel együtt is csak legfeljebb 11 él volna. Ezzel minden esetet elintéztünk és megmutattuk, hogy ha 12 él van, akkor van egy
C4
a gráfban.
Ha három háromszöget egy-egy pontjánál ,,összeragasztunk" (l. megint csak a a
3.18. feladat c) részét), majd egy új pontot összekötünk két különböző háromszög egy-egy ,,szabad" csúcsával, akkor olyan nyolcpontú, 11 élű gráfot kapunk, amelyben nincs
C4
.
Ezzel beláttuk, hogy
e4
(8)=11.
c) Legyen
G egy kilencpontú, 14 élű egyszerű gráf. Az ilyen gráfban van egy legalább negyedfokú pont. Másrészt ha van egy legfeljebb másodfokú pontja, akkor hagyjuk el a belőle induló élekkel együtt, így egy olyan nyolcpontú gráfot kapunk, amelynek legalább 12 éle van, tehát b) szerint van benne négy hosszú kör.
Marad az az eset, ha minden pont foka legalább három. Ekkor viszont egyetlen kivétellel minden pont foka három, tehát hat pont foka 3, egy ponté 4. Legyen a negyedfokú pont
x, s megint jelöljük
Sx
-szel a négy szomszédjának a halmazát,
Nx
-szel a négy ,,nem-szomszédjának" a halmazát. Az
Sx
-ből induló élek száma a) szerint legfeljebb 10, tehát
Nx
-ben legalább négy él fut. Ezek között vagy van egy
C4
, vagy van egy olyan pont, amelyből mind a három további
Nx
-beli ponthoz fut él (l. a
3.18. feladatot). De akkor ebből a pont már nem futhat él
Sx
-be. A többbi háromból is csak egy-egy él futhat
Sx
-be, tehát
Sx
pontjaiból legfeljebb
4+2+3=9 él indul. Ez viszont az
Nx
-ben futó élekkel együtt is csak 13 él volna.
Ezzel beláttuk, hogy minden kilencpontú, 14 élű egyszerű gráfban van
C4
.
A megoldásból kapunk egy példát olyan gráfra is, amely 13 élű, de nincs benne
C4
. Ezt némileg átrajzolva a következő gráfot kapjuk: Összeragasztunk két ötszöget egy élénél, ez eddig nyolc pont és kilenc él. A kilencedik pontot összekötjük az ötszögek összeragasztott élével szemközti csúccsal, és ezek egy-egy szomszédjával, de arra kell vigyázni, hogy ne keletkezzen négyszög, vagyis hogy a gráf ne legyen szimmetrikus az összeragasztott élre. Pontosan leírva: a gráf pontjai legyenek az
x,y,z,
u1
,
u2
,
u3
,
v1
,
v2
,
v3
pontok. A két összeragasztott ötszög
xyu1
u2
u3
x és
xyv1
v2
v3
x. A
z pont össze van kötve az
u2
,
u3
,
v2
,
v1
pontokkal.