Teorema cinci culori

Teorema cu cinci culori este o versiune slăbită a teoremei cu patru culori : vârfurile oricărui graf plan pot fi colorate în cinci culori, astfel încât oricare două vârfuri adiacente să fie de culori diferite (această metodă de colorare este numită corectă în matematică) sau , ceea ce este la fel, graficul planar al numărului cromatic cel mult 5. Dovedit la sfârșitul secolului al XIX-lea de Percy Heawood .

Dovada

Spre deosebire de teorema celor patru culori, demonstrația este destul de compactă. Se realizează prin inducție asupra numărului de vârfuri ale grafului. Baza inducției este faptul că, pentru , se pot colora pur și simplu vârfurile cu culori diferite. $V<6$

Pentru un pas inductiv, se arată că dacă pentru un grafic dintr-un vârf toate graficele plane cu vârfuri pot fi colorate corect cu 5 culori, atunci graficul în sine poate fi colorat cu 5 culori. Pentru a face acest lucru, folosim corolarul din formula lui Euler că într-un graf plan există un vârf de grad mai mic decât . Deoarece graficul este colorat în mod corect, sunt posibile două opțiuni: 1) dacă gradul este mai mic sau vreo două vârfuri învecinate sunt colorate în aceeași culoare (în acest caz, există o culoare în care niciunul dintre vârfurile învecinate nu este colorat , iar apoi puteți picta la această culoare, iar colorarea va fi corectă) 2) gradul vârfului este egal și toate vârfurile adiacente acestuia sunt colorate în culori diferite. $G$ $V+1$ $V$ $u$ $6$ $G\setminus \{u\)$ $5$ $u$ $5$ $u$ $u$ $u$ $u$ $5$

Pentru a doua opțiune, cinci vârfuri adiacente sunt numerotate în ordinea ocolirii marginilor de ieșire corespunzătoare în sensul acelor de ceasornic: ; for denotă culoarea vârfului ; un subgraf al unui grafic fără este definit ca un subgraf care conține toate vârfurile colorate cu culorile vârfurilor și . Sunt luate în considerare următoarele două cazuri: $u$ ${\displaystyle v_{1},v_{2},v_{3},v_{4},v_{5))$ $c_{i}$ $v_{i}$ $H_{ij)$ $G$ $u$ $v_{i}$ $v_{j}$

1. Vârfurile și se află în diferite componente conexe ale graficului . În acest caz, este posibil să recolorați nodurile din aceeași componentă ca , după cum urmează: recolorați toate nodurile de culoare la culoare și toate nodurile de culoare la culoare . Colorarea graficului fără va rămâne în continuare corectă, dar acum vârful va fi colorat cu culoarea , și nu cu , ceea ce înseamnă că puteți colora vârful cu culoarea și obțineți colorarea necesară a graficului . $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. Vârfurile și se află în aceeași componentă conexă a graficului . Apoi, între vârfuri și există o cale în grafic . Împreună cu vârful și muchiile , această cale formează și un ciclu . Deoarece graficul este planar și este un ciclu care nu se intersectează singur, atunci, conform teoremei lui Jordan , el împarte planul în componente conexe (externe și interne), iar punctele și vor fi în componente diferite și, prin urmare, există nu există o cale de la la în grafic . Atunci și sunt în diferite componente conectate ale graficului și, în mod similar cu raționamentul din Cazul 1, putem recolora vârfurile din aceeași componentă conectată a graficului , după cum urmează: toate vârfurile de culoare sunt recolorate la culoarea și toate vârfurile culorii sunt recolorate la culoare , iar apoi vârful este recolorat la culoare și obține colorarea dorită a graficului . $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}$ $v_{4)$ $v_{2}$ $v_{4)$ $H_{24)$ $v_{2}$ $v_{4)$ $H_{24)$ $H_{24)$ $v_{2}$ $c_{2}$ $c_{4}$ $c_{4}$ $c_{2}$ $u$ $c_{2}$ $G$