Ötszín-tétel

Ez a szócikk nem tünteti fel a független forrásokat, amelyeket felhasználtak a készítése során. Emiatt nem tudjuk közvetlenül ellenőrizni, hogy a szócikkben szereplő állítások helytállóak-e. Segíts megbízható forrásokat találni az állításokhoz! Lásd még: A Wikipédia nem az első közlés helye.

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.

Először is, az adott térképhez rendeljünk hozzá egy ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle V}$ csúcsnak, amiben legfeljebb öt él találkozik, majd kihasználja, hogy ${\displaystyle 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 ${\displaystyle V}$ csúcspontot a ${\displaystyle G}$ gráfból. Az így nyert ${\displaystyle G^{'}}$ gráfnak kevesebb csúcspontja van, mint ${\displaystyle 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 ${\displaystyle V}$-vel szomszédosak voltak, legyenek ezek ${\displaystyle V_{1}}$, ${\displaystyle V_{2}}$, ${\displaystyle V_{3}}$, ${\displaystyle V_{4}}$ és ${\displaystyle V_{5}}$. Ha nem használtuk fel mind az öt színt, akkor nyilvánvalóan ki tudjuk színezni a ${\displaystyle V}$ csúcspontot úgy, hogy a gráfot 5 színnel tudjuk színezni.

Így tehát feltehetjük, hogy a ${\displaystyle V_{1}}$, ${\displaystyle V_{2}}$, ${\displaystyle V_{3}}$, ${\displaystyle V_{4}}$ és ${\displaystyle V_{5}}$ csúcspontok az 1, 2, 3, 4, 5 jelű színekkel vannak színezve.

Ezután tekintsük ${\displaystyle G^{'}}$ azon ${\displaystyle G_{13}}$ 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 ${\displaystyle V_{1}}$ és a ${\displaystyle V_{3}}$ csúcspontok a ${\displaystyle G_{13}}$ részgráf nem összefüggő részén vannak, fordítsuk meg ${\displaystyle V_{1}}$ színezését úgy, hogy az 1-es számú színt a ${\displaystyle V}$ csúcshoz rendeljük hozzá.

Ha viszont ${\displaystyle V_{1}}$ és ${\displaystyle V_{3}}$ csúcspontok a ${\displaystyle G_{13}}$ összefüggő részén vannak, akkor találhatunk a ${\displaystyle G_{13}}$ 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 ${\displaystyle G^{'}}$ azon ${\displaystyle G_{24}}$ 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 ${\displaystyle G_{24}}$ részgráfon és a ${\displaystyle V}$ csúcspontot mondjuk 2 színűre színezni, vagy a ${\displaystyle V_{2}}$ és a ${\displaystyle V_{4}}$ 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 ${\displaystyle G_{13}}$ részgráfban konstruáltunk.

Tehát ${\displaystyle G}$ valójában kiszínezhető öt színnel, így az eredeti feltételezésünk hamis volt.

• Négyszín-tétel