Feladat: 12.13.
* Láttuk már, hogy egy
2n pontú gráfban minden pont foka legalább
n, akkor a gráf összefüggő, sőt kétszeresen összefüggő. (Lásd a
GR.II.1.8. feladatot.) Most bizonyítsuk be az alábbi tételt, amelyből mind a
9.11. feladat állítása, mind ezek az állítások következnek.
Dirac tétele. Ha egy
2n pontú gráfban minden pont foka legalább
n, akkor a gráfnak van Hamilton-köre.
Megoldás: 12.13
Legyen
G egy
2n pontú gráf, amelyben minden pont foka legalább
n, és tegyük fel, hogy van Hamilton-útja, azaz van a gráfban
P=
x1
x2
…
x2n-1
x2n
út. Nézzük
x1
szomszédjait a gráfban, legyenek ezek
x2
=
x
i1
,
x
i2
,
x
i3
,…,
x
im
. A feladat feltétele szerint
m≥n. Nézzük azokat a pontokat
P-n, amelyek közvetlenül megelőzik ezeket a pontokat. Ha
x2n
össze van kötve közülük valamelyikkel, tehát valamelyik
x
ij
-1
-gyel, akkor a következő Hamilton-körhöz jutunk:
x1
…
x
ij
-1
x2n
x2n-1
…
x
ij
x1
.
|
(Amennyiben
ij
=2, akkor egyszerűen a
P út záródik körré az
x1
x2n
éllel.)
Ha viszont
x2n
ezek egyikével sem volna összekötve, akkor a gráfból legalább
n ponttal nem volna összekötve, így legfeljebb
n-1 szomszédja volna, ami ellentmond a feladat feltételének.
Ezzel beláttuk, hogy ha a
G gráfra teljesül a feladat feltétele és van benne Hamilton-út, akkor van benne Hamilton-kör is.
Tegyük fel ezután, hogy egy
2n pontú gráfban minden pont foka legalább
n, de nincs benne Hamilton-kör. Ha van olyan él a komplementer gráfban, amely nem zár be Hamilton-kört a gráfunkban, akkor vegyük hozzá a gráfunkhoz. Ezzel a feladat feltételét nem sértjük meg, hiszen egyetlen pont foka sem csökken. Ismételjük ezt az eljárást addig, amíg már egy olyan, úgynevezett ,,kritikus"
G gráfhoz érünk, amelyben minden pont foka továbbra is legalább
n, s amelyre már igaz a következő:
A
G gráfban nincs Hamilton-kör, de bármely még nem szereplő élt behúzva a gráfban már keletkezik Hamilton-kör.
Nyilvánvaló, hogy egy ilyen kritikus gráfban kell lennie Hamilton-útnak (bármely két, be nem húzott pontja között). Ez viszont ellentmond a korábban bizonyított állításunknak, hogy akkor van benne Hamilton-út is.
Megjegyzés. Ez a bizonyítás mintegy ,,folytatása", vagy finomítása a
12.10. bizonyításának. Másrészt itt a ,,vegyük a legnagyobbat" gondolatnak egy újabb felhasználását látjuk: a(z egyik) ,,legnagyobb" olyan gráfot vesszük, amely tartalmazza eredeti gráfunkat, és teljesít egy bizonyos tulajdonságot (esetünkben: nem tartalmaz Hamilton-kört). Az ilyen, megadott tulajdonságra ,,kritikus" gráfok vizsgálata sokszor segít gráfelméleti problémák megoldásánál. Mi is használjuk, pl. a
14.24. feladat bizonyításában.
Ebben a bizonyításban tehát használtuk a skatulyaelv és a ,,vegyük a legnagyobbat" elv egy-egy finomabb formáját.