Öt szín tétel

Az ötszínű tétel a négyszínű tétel gyengített változata : bármely síkgráf csúcsai öt színnel színezhetők úgy, hogy bármely két szomszédos csúcs különböző színű legyen (ezt a színezési módszert a matematikában helyesnek nevezik), ill. , ami ugyanaz, a kromatikus szám síkgráfja legfeljebb 5. A 19. század végén Percy Heawood bizonyította .

Bizonyítás

A négy szín tétellel ellentétben a bizonyítás meglehetősen kompakt. Indukcióval hajtják végre a gráf csúcsainak számát. Az indukció alapja az a tény, hogy a esetén egyszerűen színezhetjük a csúcsokat különböző színekkel. $V<6$

Egy induktív lépésnél megmutatjuk, hogy ha egy csúcsból származó gráfhoz az összes csúcsú síkgráf 5 színnel helyesen színezhető, akkor maga a gráf 5 színnel színezhető. Ehhez az Euler -képletből azt a következtetést használjuk, hogy egy síkgráfban van egy -nél kisebb fokú csúcs . Mivel a gráf megfelelő módon van színezve , két lehetőség lehetséges: 1) ha a fok kisebb vagy néhány szomszédos csúcs azonos színűre van színezve (ebben az esetben van olyan szín, amelyben a szomszédos csúcsok egyike sem színes , majd festhet erre a színre, és a színezés helyes lesz) 2) a csúcs foka egyenlő , és a vele szomszédos összes csúcs különböző színnel van színezve. $G$ $V+1$ $V$ $u$ $6$ ${\displaystyle G\setminus \{u\))$ $5$ $u$ $5$ $u$ $u$ $u$ $u$ $5$

A második lehetőségnél öt szomszédos csúcsot számozunk meg a megfelelő kimenő élek megkerülésének sorrendjében az óramutató járásával megegyező irányban: ; for a csúcs színét jelöli ; egy gráf részgráfja anélkül , hogy olyan részgráf, amely tartalmazza az összes csúcsot és a csúcsszínekkel színezett csúcsokat . A következő két esetet vizsgáljuk: $u$ ${\displaystyle v_{1},v_{2},v_{3},v_{4},v_{5))$ $c_{i}$ $v_{i}$ ${\displaystyle H_{ij))$ $G$ $u$ $v_{i}$ $v_{j}$

1. A és csúcsok a gráf különböző összefüggő komponenseiben helyezkednek el . Ebben az esetben lehetőség van ugyanabból a komponensből a csúcsok átszínezésére a következőképpen: minden színcsúcsot színre színezze át , és minden színcsúcsot színre . A nélküli gráf színezése továbbra is helyes marad, de most a csúcs a színnel lesz színezve , és nem a -val, ami azt jelenti, hogy a színnel színezheti a csúcsot , és megkaphatja a gráf kívánt színezését . $v_{1}$ $v_{3}$ $H_{13}$ $v_{1}$ $c_{1}$ $c_{3}$ $c_{3}$ $c_{1}$ $G$ $u$ $v_{1}$ $c_{3}$ $c_{1}$ $u$ $c_{1}$ $G$

2. A és csúcsok a gráfnak ugyanabban az összefüggő komponensében vannak . Ekkor a csúcsok és a csúcsok között van egy út a gráfban . A csúcsgal és élekkel együtt ez az út is ciklust alkot . Mivel a gráf síkbeli, és nem önmagát metsző kör, ezért a Jordan-tétel szerint a síkot összefüggő (külső és belső) komponensekre osztja, a pontokat pedig különböző komponensekben, és ezért ott nincs elérési út innentől a grafikonon . Ekkor és a gráf különböző összefüggő komponenseiben vannak , és az 1. esetből származó érveléshez hasonlóan a gráf ugyanabból az összekapcsolt komponenséből újraszínezhetjük a csúcsokat a következőképpen : minden színcsúcs átszíneződik a színre , és a szín minden csúcsa átszíneződik a színre , majd a csúcs átszíneződik , hogy színt kapjon, és megkapja a gráf kívánt színét . $v_{1}$ $v_{3}$ $H_{13}$ $v_{1}$ $v_{3}$ $H_{13}$ $u$ $(v_{3},u)$ $(u,v_{1})$ $C_{13}$ $G$ $C_{13}$ $C_{13}$ $2$ $v_{2}$ ${\displaystyle v_{4))$ $v_{2}$ ${\displaystyle v_{4))$ ${\displaystyle H_{24))$ $v_{2}$ ${\displaystyle v_{4))$ ${\displaystyle H_{24))$ ${\displaystyle H_{24))$ $v_{2}$ $c_{2}$ $c_{4}$ $c_{4}$ $c_{2}$ $u$ $c_{2}$ $G$