Megoldás: 8.26
A
8.25. feladat a) részének megoldásmenetét követjük. De most a pontszámra vonatkozó teljes indukciót is alkalmazunk.
n=5-re láttuk, hogy legalább öt élre van szükség, tehát a kezdő lépés biztosítva van.
Legyen
G egy
n pontú, 2-átmérőjű gráf,
n>5 és tegyük fel, hogy
n-nél kisebb gráfokra már tudjuk a feladat állítását. Legyen a
G-beli fokszám minimuma
k. Ha
k legalább négy, akkor a gráf élszáma legalább
2n, tehát nincs mit bizonyítanunk.
k=1 nem lehet, mert akkor a
8.22. feladat szerint a szomszédja telített pont volna. Tehát
k=2 vagy
k=3.
a)
k=3. Legyen
x egy harmadfokú pont és legyenek
x szomszédai
y,z,u. Legyen a további pontok halmaza
H.
H minden pontja össze van kötve
y,z,u közül legalább eggyel (mert a gráf 2-átmérőjű). Válasszunk ki
H minden pontjához egyet
y,z,u közül, amellyel össze van kötve. (L. a szélességi favázat az
ALG.II.3.3. feladatban.) Ez az
xy,xz,xu élekkel eddig
n-1 él. Hagyjuk el ezt az
n-1 élt a gráfból.
H minden pontja legalább harmadfokú, tehát a maradó gráfban még legalább másodfokú. Ez összesen legalább annyi élt jelent, amennyi
H pontjainak száma, azaz
n-4-et. Tehát összesen legalább
(n-1)+(n-4)=2n-5 éle van a gráfnak.
b)
k=2. Legyen
x egy másodfokú pont, két szomszédja legyen
y és
z. Tegyük fel először, hogy
y-nak és
z-nek nincs közös szomszédja
x-en kívül. Legyen
y további (
x-től különböző) szomszédainak halmaza
Y,
z további szomszédainak halmaza
Z. E két halmaz
x,y,z-vel együtt kiadja a gráf összes pontját, különben
x-ből nem volna minden kettő hosszú úttal elérhető. Az
xy,xz,
yY,
zZ élek együtt tehát
n-1 élt adnak. Két esetet választunk szét.
b1) Ha
x az egyetlen másodfokú pont a gráfban, akkor ennek az
n-1 élnek az elhagyása után
Y∪Z minden csúcsa még legalább másodfokú marad, tehát ez még legalább annyi él, ahány csúcs
Y∪Z-ben van, azaz
n-3. Ebben az esetben tehát legalább
2n-4 élt is tudunk garantálni. Ugyanez a meggondolás megy akkor is, ha
x-en kívül csak
y vagy
z volna másodfokú.
b2) Ha
Y∪Z halmazban is van egy másodfokú pont. Feltehetjük, hogy ez a pont
Y-ban van, jelöljük
y'-vel. Először legyen
u az
Y halmaz egy tetszőleges pontja. Tudjuk, hogy
u nincs összekötve
z-vel, tehát van egy közös szomszédja vele, azaz
u össze van kötve
Z valamelyik pontjával. Ez azt jelenti, hogy
Y minden pontjából fut legalább egy él
Z-be. (Ugyanez természetesen igaz
Z pontjaira is: belőlük is fut legalább egy-egy él
Y-ba.) Vegyük most az
y' pontot. Mivel másodfokú és egyik szomszédja
y, így a másik szomszédja biztosan
Z-ben van, legyen ez a szomszédja
z'. Mivel a gráf átmérője 2,
y'-ből is minden pontot el kell érnünk kettő hosszú úttal. Ha
y-on keresztül indulunk, akkor csak
Y∪{x} pontjaihoz jutunk el. Tehát
Z pontjaihoz csak
z'-n keresztül vezethet az út. Ez viszont azt jelenti, hogy
z' össze van kötve
Z minden más pontjával. Ez
|Z|-1 él. Másrészt
Y minden pontjából is indul legalább egy-egy él
Z-be, ez további
|Y| él, összesen eddig
|Z|+|Y|-1=n-4 él. Hozzávéve az
xy,xz,
yY és
zZ éleket, ami további
n-1 él, összesen ismét legalább
2n-5 élt kapunk.
Marad az az eset, amikor
x másodfokú pont, és két szomszédjának,
y-nak és
z-nek van közös szomszédja
x-en kívül is. Könnyen látható, hogy ebben az esetben
G-x is 2-átmérőjű, és pontszáma
n-1. Ha nincs telített pontja, akkor alkalmazható rá az indukciós feltétel, azaz legalább
2n-7 éle van, s ehhez hozzávéve az
xy,xz éleket megint legalább
2n-5 élt kapunk.
Befejezésül azt kell még megvizsgálnunk, mi van, ha a
G-x gráfban van telített pont. Sem
y, sem
z nem lehet telített pont, mert akkor
G-ben is telített pont volna, amit kizártunk. Ha viszont egy
y-tól és
z-től különböző
u pont a telített pont, akkor
u-ból
n-2 él indul ki. Ez az
xy és
xz éllel együtt már
n él a
G gráfban. Vegyünk egy tetszőleges további
v pontot. Mivel
v nincs összekötve
x-szel, vagy
y-on keresztül érhető el
x-ből, vagy
z-n keresztül. Ez minden
v pontra egy-egy további
yv vagy
zv élt jelent, összesen még legalább
n-4 élt. Ebben az esetben tehát legalább
2n-4 élt is tudunk garantálni.
Ezzel a bizonyítást minden esetben befejeztük.