Viiden värin lause

Viiden värin teoreema on heikennetty versio nelivärilauseesta : minkä tahansa tasograafin kärjet voidaan värjätä viidellä värillä niin, että mitkä tahansa kaksi vierekkäistä kärkeä ovat erivärisiä (tätä värjäysmenetelmää kutsutaan matematiikassa oikeaksi), tai , mikä on sama, kromaattisten lukujen tasograafi enintään 5. Todisti 1800-luvun lopulla Percy Heawood .

Todiste

Toisin kuin neljän värin lause, todistus on melko kompakti. Se suoritetaan induktiolla graafin kärkien lukumäärälle. Induktion perustana on se, että , voi yksinkertaisesti värittää kärjet eri väreillä. $V<6$

Induktiivisella askeleella on osoitettu, että jos graafille kärjestä kaikki tasograafit, joissa on huippuja, voidaan värjätä oikein 5 värillä, niin itse graafi voidaan värjätä 5 värillä. Tätä varten käytämme Eulerin kaavan seurausta, että tasograafissa on aste pienempi kuin . Koska graafi on väritetty oikealla tavalla, kaksi vaihtoehtoa on mahdollista: 1) jos aste on pienempi tai jotkut kaksi vierekkäistä kärkeä väritetään samalla värillä (tässä tapauksessa on väri, jossa yksikään naapuripisteistä ei ole värillinen , ja sitten voit maalata tähän väriin, ja väritys on oikea) 2) kärjen aste on yhtä suuri ja kaikki sen vieressä olevat kärjet on värjätty eri väreillä. $G$ $V+1$ $V$ $u$ $6$ $G\setminus \{u\}$ $5$ $u$ $5$ $u$ $u$ $u$ $u$ $5$

Toisessa vaihtoehdossa viisi vierekkäistä kärkeä numeroidaan siinä järjestyksessä, että vastaavat lähtevät reunat ohitetaan myötäpäivään: ; for tarkoittaa kärjen väriä ; aligraafi graafista ilman määritellään aligraafiksi, joka sisältää kaikki kärjet, jotka on värjätty kärkiväreillä ja . Seuraavat kaksi tapausta tarkastellaan: $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. Huiput ja sijaitsevat graafin eri yhdistetyissä komponenteissa . Tässä tapauksessa on mahdollista värjätä pisteet uudelleen samasta komponentista seuraavasti: väritä kaikki väripisteet uudelleen väriksi ja kaikki väripisteet väriksi . Kuvaajan väritys ilman säilyy edelleen oikeana, mutta nyt kärki värjätään värillä , ei -värillä, mikä tarkoittaa, että voit värittää kärjen värillä ja saada graafin vaaditun värityksen . $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. Huiput ja sijaitsevat graafin samassa yhdistetyssä komponentissa . Sitten pisteiden ja välillä on graafissa polku . Yhdessä kärjen ja reunojen kanssa tämä polku muodostaa myös syklin . Koska kuvaaja on tasomainen ja ei-leikkaava sykli, niin se jakaa Jordanin lauseen mukaan tason yhdistettyihin komponentteihin (ulkoisiin ja sisäisiin), ja pisteet ja tulevat olemaan eri komponenteissa, joten ei ole polkua kohteesta kohteeseen kaaviossa . Sitten ja ovat graafin eri yhdistetyissä komponenteissa , ja tapauksen 1 päättelyn tapaan voimme värjätä graafin samasta yhdistetystä komponentista olevat kärjet uudelleen seuraavasti : kaikki väripisteet värjätään uudelleen väriin , ja kaikki värin kärjet värjätään uudelleen väriin ja sitten kärki värjätään uudelleen värjäykseen ja saadakseen graafin haluttu väritys . $v_{1}$ $v_{3}$ $H_{13}$ $v_{1}$ $v_{3}$ $H_{13}$ $u$ ${\näyttötyyli (v_{3},u)}$ ${\näyttötyyli (u,v_{1})}$ $C_{13}$ $G$ $C_{13}$ $C_{13}$ $2$ $v_{2}$ ${\displaystyle v_{4))$ $v_{2}$ ${\displaystyle v_{4))$ $H_{24}$ $v_{2}$ ${\displaystyle v_{4))$ $H_{24}$ $H_{24}$ $v_{2}$ $c_{2}$ $c_{4}$ $c_{4}$ $c_{2}$ $u$ $c_{2}$ $G$