Ötszín-tétel
A Wikipédiából, a szabad lexikonból.
A gráfelméletben az ötszín-tétel kimondja, hogy bármilyen térkép kiszínezhető legfeljebb öt szín felhasználásával. Ez természetesen következik az erősebb négyszín-tételből, de sokkal könnyebben bizonyítható annál. Alfred Kempe 1879-es, a négyszín-sejtésre adott hibás bizonyításának felhasználásával Percy John Heawoodnak sikerült először bizonyítania.
[szerkesztés] A bizonyítás menete
Először is, az adott térképhez rendeljünk hozzá egy G gráfot, úgy hogy annak minden csúcspontja a térkép egy régiójának feleljen meg, és két csúcspontot akkor és csak akkor kössünk össze, ha a megfelelő régióknak közös határvonaluk van. Így a problémát átalakítottuk egy gráfszínezési problémává: úgy kell a gráf csúcspontjait kiszínezni, hogy egyik éle se kössön össze azonos színű pontokat.
A bizonyítás felteszi egy G minimális ellenpélda-gráf létezését, tehát a legkisebb gráfét, amit nem lehet öt színnel kiszínezni. Ezután az Euler-karakterisztika felhasználásával megmutatja, hogy ebben a gráfban léteznie kell egy V csúcsnak, amiben legfeljebb öt él találkozik, majd kihasználja, hogy G síkba rajzolható gráf, tehát lerajzolható a síkban anélkül, hogy egymást metsző éleket rajzolnánk.
Most távolítsuk el V csúcspontot a G gráfból. Az így nyert V' gráfnak kevesebb csúcspontja van, mint G-nek, tehát indukcióval feltehetjük, hogy ugyanúgy kiszínezhető öt színnel. Ezután tekintsük az öt csúcsot, amelyek V-vel szomszédosak voltak, legyenek ezek V1, V2, V3, V4 és V5. Ha nem használtuk fel mind az öt színt, akkor nyilvánvalóan ki tudjuk színezni a V csúcspontot úgy, hogy a gráfot 5 színnel tudjuk színezni.
Így tehát feltehetjük, hogy a V1, V2, V3, V4 és V5 csúcspontok az 1, 2, 3, 4, 5 jelű színekkel vannak színezve.
Ezután tekintsük V' azon G13 részgráfját, ami csak azokat a csúcspontokat tartalmazza, amelyek színe 1-es vagy 3-as, és a köztük lévő éleket. Ha a V1 és a V3 csúcspontok a G13 részgráf nem összefüggő részén vannak, fordítsuk meg V1 színezését úgy, hogy az 1-es számú színt a V csúcshoz rendeljük hozzá.
Ha viszont V1 és V3 csúcspontok a G13 összefüggő részén vannak, akkor találhatunk a G13 részgráfban őket összekötő utat, tehát élek és csúcspontok olyan sorozatát, ami csak az 1-es és a 3-as színekkel van színezve.
Ezután tekintsük a V' G24 részgráfját, ami csak a 2-es vagy 4-es színű csúcspontokat és a köztük lévő éleket tartalmazza, és alkalmazzuk az 1 és 3 színeknél használt logikai lépéseket. Ezután vagy meg tudjuk fordítani a színezést a G24 részgráfon és a V csúcspontot mondjuk 2 színűre színezni, vagy a V2 és a V4 csúcsok között létezik út, ami csak 2-es vagy 4-es színű csúcspontokon megy át. Ez utóbbi lehetőség teljesen abszurd, hiszen ez az út keresztezné azt az utat, amit a G13 részgráfban konstruáltunk.
Tehát G valójában kiszínezhető öt színnel, így az eredeti feltételezésünk hamis volt.
Based on work by