Triviális átszínezés: Vegyünk egy v csúcsot. Szomszédai között elóforduló színek halmaza legyen T. Legyen S-T egy v színétõl különbözõ eleme s. v színét változtassuk át s-re.

Kempe-átszínezés (az átszínezés elnevezését Alfred Bray Kempe angol matematikusról kapta): Vegyünk két színt s-et és t-t. Legyen G_s,t az s és t színû csúcsok és a köztük haladó élek által alkotott gráf. Legyen C ennek egy komponense. C csúcsain cseréljük fel az s és t színeket.

Ha a színcserét a teljes G_s,t gráf csúcshalmazá;n elvégezzük akkor csupán a két szín nevének felcseréléset végezzük el, a színezés lényegében nem változik. Ha C egyetlen egy csúcs, akkor a Kempe-átszínezés egy triviális átszínezés lesz.

A következõ algoritmikus sémát követjük. Ismét vegyük csúcsaink egy sorrendjét és minden csúcs színét sorban határozzuk meg. Ha az egyik csúcshoz jutunk és egy új, nagy színt jelöl ki a mohó színezés, akkor ezt a színt nem jelöljük ki gondolkozás nélkül, hanem a már színezett csúcsok által feszített részgráfot megpróbáljuk átszínezni. Ha egy átszínezés ki kerüli az új szín használatát, akkor ezen átszínezést bõvítjük. Ha nem, akkor esetleg az átszínezett gráf további átszínezéseivel próbálkozhatunk.

A fenti séma sokféleképpen megvalósítható. Erre mutatunk példákat.

Vegyük az egyszerû síkgráfok csúcsainak azon sorrendjét, amelyben minden csúcsot legfeljebb öt szomszédja elõzi meg. Ezt a sorrendet követve színezzünk öt színnel. Egyetlen módon akadhatunk el. Az éppen színezendõ v csúcsnak már öt színezett (a sorrendben korábbi) szomszédja van, amelyek különbözõ színt kaptak. Ekkor próbáljuk meg Kempe-átszínezésekkel elkerülni a hatodik szín felhasználását.

Az öt színezett szomszéd legyen v₁, v₂, v₃, v₄, v₅, ahol az indexek jelöljék az egyes szomszédok színeit, de egyben G egy rögzített lerajzolásánál a v csúcs körüli geometriai sorrendet is tükrözzék. G_1,3-ban legyen C a v₁ csúcs komponense.

1. eset: Ha C nem tartalmazza a v₃ csúcsot, akkor a megfelelõ Kempe átszínezés v₁-et átszínezi 3-as színûre, míg v további szomszédainak színe megmarad. Így ezen átszínezés után v színe lehet 3.

2. eset: Ha C tartalmazza a v₃ csúcsot, akkor a Kempe-átszínezés nem ad túl sok újat. Ennek ellenére hasznos lesz összefoglalni mit tudunk ekkor.

Ekkor viszont van egy P út, amely összeköti a v₁ és v₃ csúcsokat és pontjai alternálva 1-es és 3-as színekkel színezve vannak. A P út két végpontja a v csúcs két szomszédja. Ez a két szomszédság lehetóséget ad a P út egy körrré zárására a v csúcs segítségével. Legyen P' az így kapott kör. Gráfunk korábban lerögzített lerajzolásában a P' kör egy önmagát nem metszõ zárt görbének felel meg,a mley a síkot két részre osztja: egy korlátosra és egy nem korlátosra. v szomszédainak elnevezésénél az indexek ey geometriai sorrendet követtek így könnyen meggondolható, hogy v₂ és v₄ a fenti két tartományokat tekintve különbözõkbe esik.

Gondolatmenetünket megismételhetjük a v₂ és v₄ csúcsokkal és 2, iletve 4 színekkel. Elméletileg ekkor is lesz egy 1., illetve 2. eset. Az 1. esetben egy Kempe átszínezés után megnyílik a lehetõség v színezésére új szín felhasználása nélkül. A bizonyítás befejezéséhez azt kell észrevenni, hogy a P' kör bizonyítja, hogy a 2. eset most nem állhat fent.

Legyen G egy D maximális fokú összefüggõ gráf, amely sem páratlan hosszú kör, sem teljes gráf. Be fogjuk látni, hogy G D színnel jól színezhetõ. Ehhez feltehetõ, hogy D legalább 3.

Vegyük csúcsaink egy tetszõleges sorrendjét és kezdjük el eszerint színezni gráfunkat egy D színt tartalmazó palettával. Egyetlen problémával talákozhatunk: az aktuálisan színezendõ v csúcsnak már D darab színezett szomszédja van, amelyek különbözõ színt kaptak. Legyenek ezek v₁, v₂, v₃,..., v_D-1, v_D, ahol az indexek a megfelelõ csúcs színét adják.

1. lehetõség: A G_i,j gráf v_i-t tartalmazó C_i,j komponenséhez nem tartozik hozzá a v_j csúcs.

Ekkor a megfelelõ Kempe-átszínezés után v új szín felhasználása nélkül kiszínezhetõ.

2. lehetõség: Valamelyik C_i,j gráf nem azonos egy v_i-t és v_j-t összekötõ P_i,j úttal.

Az 1. lehetõség után már tudjuk, hogy A C_i,j gráf tartalmaz egy v_i-t és v_j-t összekötõ P_i,j útat. tegyük fel, hogy ez nem a teljes C_i,j gráf. Ekkor P_i,j-n v_i felöl elindulva lesz egy legelsõ u csúcs, amelynek van P_i,j-n kívüli, C_i,j-beli szomszédja u '. Belátjuk, hogy u triviális módon átszínezhetõ. Valóban, ha u a P_i,j út belsõ pontja, akkor van három azonos színû szomszédja: az út menti két szomszéd és u '. Ennyi színismétlõdés a legfeljebb D szomszéd között garantálja az átszínezés lehetõségét. Ha u a P_i,j út egyik végpontja, akkor csak kettõ azonos színû szomszédját látjuk: az út menti szomszéd és u ', azonban egyik szomszédja, v színezetlen. Ennyi is elég a garantált átszínezhetõséghez.

Ha u a P_i,j út egyik végpontja, akkor v egyik szomszédját színeztük át a többi szomszéd színének meghagyásával. Ezek után v színezhetõ új szín felhasználása nélkül. Ha u a P_i,j út belsõ csúcsa, akkor az új színezés olyan, hogy rá az 1. lehetõség teljesül ezen i és j színpárral, és így készen vagyunk.

3. lehetõség: Valamelyik P_i,j út áthalad egy v_k ponton (k különbözik i-tõl és j-tõl is).

Ekkor a korábbi módon v_k átszínezhetõ v többi szomszédjának színtartásával és készen vagyunk.

4. lehetõség: Valamely két P_i,j és P_k,l utak közös u belsõ ponton haladnak át.

Ekkor u átszínezhetõ és ezzel egy olyan színezéshez jutunk, amelyre az 1. lehetõség teljesül. Így készen vagyunk.

Maradék lehetõség: Ha a fenti négy lehetõség egyike sem teljesül, akkor a D szomszédot (^N₂) darab út köti össze amelyek belsõ pontjai páronként diszjunktak egymástól és a {v₁, v₂, ..., v_D} halmaztól. Továbbá ezek az utak a teljes C_i,j gráfok. Mivel gráfunk nem a teljes D+1 pontú gráf ezért a fenti útrendszernek legalább az egyeik eleme nem egy hosszú.

Ebben az esetben a következõt tehetjük: Vegyük az egyik legalább kettõ hosszú utat. Feltehetõ, hogy ez P_1,2. legyen u a v₂ csúcs P_1,2 menti szomszédja. Alkalmazzuk a Kempe-átszínezést a C_2,3(=P_2,3) gráfra. Ekkor a v₂ csúcs a 3 színt fogja kapni és szomszédja u 1 színû lesz. Ez azt jelenti, hogy átszínezés után u egyrészt belekerül a C_1,3 gráfba, de benne marad a C_1,2 gráfban is. Tehát az átszínezett gráfra biztos nem a Maradék lehetõség áll fenn. A korábbi négy lehetõség mindegyik olyan, hogy lehetõséget ad az új szín használatánal elkerülésére.