Femfärgssats

Femfärgssatsen är en försvagad version av fyrfärgssatsen : hörnen på vilken plan graf som helst kan färgas i fem färger så att två intilliggande hörn har olika färg (denna färgningsmetod kallas korrekt i matematik), eller , vad är detsamma, den kromatiska talplana grafen högst 5. Bevisad i slutet av 1800-talet av Percy Heawood .

Bevis

Till skillnad från fyrafärgssatsen är beviset ganska kompakt. Det utförs genom induktion på antalet grafens hörn. Grunden för induktionen är det faktum att man helt enkelt kan färga topparna med olika färger. $V<6$

För ett induktivt steg visas att om för en graf från en vertex alla plana grafer med hörn kan färgas korrekt med 5 färger, så kan själva grafen färgas med 5 färger. För att göra detta använder vi följden från Eulers formel att det i en plan graf finns en vertex med grad mindre än . Eftersom grafen är färgad på rätt sätt är två alternativ möjliga: 1) om graden är mindre eller om två närliggande hörn är färgade i samma färg (i det här fallet finns det en färg där ingen av de angränsande hörnen är färgad , och sedan kan du måla till denna färg, och färgningen blir korrekt) 2) graden av vertex är lika och alla hörn intill den är färgade i olika färger. $G$ $V+1$ $V$ $u$ $6$ ${\displaystyle G\setminus \{u\))$ $5$ $u$ $5$ $u$ $u$ $u$ $u$ $5$

För det andra alternativet numreras fem angränsande hörn i den ordningsföljd de förbigår motsvarande utgående kanter medurs: ; för betecknar spetsens färg ; en subgraf i en graf utan definieras som en subgraf som innehåller alla hörn färgade av vertexfärger och . Följande två fall beaktas: $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. Topparna och ligger i olika sammankopplade komponenter i grafen . I det här fallet är det möjligt att färga om hörn från samma komponent som , enligt följande: färga om alla hörn av färg till färg , och alla hörn av färg till färg . Färgen på grafen utan kommer fortfarande att förbli korrekt, men nu kommer vertexet att färgas med färgen , och inte med , vilket innebär att du kan färga vertexet med färgen och få önskad färgning av grafen . $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. Topparna och ligger i samma sammankopplade komponent i grafen . Sedan mellan hörnen och det finns en bana i grafen . Tillsammans med spetsen och kanterna bildar denna väg också en cykel . Eftersom grafen är plan och är en icke-självkorsande cykel, så delar den enligt Jordan-satsen upp planet i anslutna komponenter (externa och interna), och punkterna och kommer att finnas i olika komponenter, och därför finns det är ingen väg från till i grafen . Sedan och finns i olika sammankopplade komponenter i grafen , och på samma sätt som resonemanget från fall 1 kan vi färga om hörnen från samma anslutna komponent i grafen enligt följande: alla färgpunkter färgas om till färgen , och alla hörn i färgen färgas om till färgen , och sedan färgas vinkeln om till färg och får önskad färg på grafen . $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))$ $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$