A teljes gráfok színezéséhez a maximális fokszámnál eggyel több színre van szükség. Ők és a páratlan hosszú körök adják a Brooks-tétel kivételes eseteit.
Legyen véges, összefüggő gráf, ami nem teljes gráf vagy páratlan csúcsú körgráf. Jelölje a maximális fokszámát, pedig a kromatikus számát. Ekkor
= 2 -re nyilvánvaló az állítás, ugyanis ha a maximális fokszám 2, akkor vagy egy kört, vagy egy utat kapunk. Egy út vagy egy páros kör esetében 2 színnel ki tudjuk színezni a gráfot, és ha a kör páratlan hosszúságú akkor csak hárommal.
Most már feltehetjük, hogy 3. A csúcsok számára való indukcióval bizonyítjuk az állítást.
Az első lépésben azt látjuk be, hogy elég kétszeresen összefüggő gráfokat vizsgálnunk. Indirekt tegyük fel, hogy nem kétszeresen összefüggő a vizsgálandó gráfunk, ami azt jelenti hogy létezik pont, melyet elhagyva legalább két komponensre esik szét a gráfunk. Ha pontosan két komponensre esik szét, akkor rakjuk vissza mindkét komponensbe -et, és nevezzük ezeket a komponenseket és -nek. Ha több mint két komponensre esik szét, akkor maradjon továbbra is egy komponens és meg legyen az összes többi komponens és x uniója: = ( \ ) {}. A két komponensben minden csúcs fokszáma ugyanannyi marad, csak x fokszáma csökken. Tehát továbbra sem lesz egyik fokszám sem nagyobb mint , viszont foka feltétlenül kisebb lesz mindkét komponensben -nél. Ebből következik, hogy egyik komponens sem lehet + 1 pontú teljes gráf. Tehát, az indukciós feltevésünk miatt, mindkét komponens kiszínezhető színnel, és ha -et mindkét komponensben ugyanolyan színűre választjuk, akkor ha újra „összerakjuk” a gráfot akkor az eredeti gráfunknak egy színnel való jó színezését kapjuk.
Második lépésben pedig azt igazoljuk, hogy elég háromszorosan összefüggő gráfokat néznünk. Ismét indirekt tegyük fel hogy egy és pont elhagyásával szétesik a gráfunk és -re. Végezzük el ugyanazt az eljárást mint az első lépésben. Itt csak akkor van gond, ha az egyik komponens minden színezése olyan hogy és egyforma színű, és a másik komponens minden színezésénél és különböző színű. Ebben az esetben nem tudjuk újra „összerakni” a gráfunkat. Ebben az esetben tekintsük a és komponenst és mindkettőben húzzunk be és között egy élt. Így és fokszáma továbbra is legfeljebb marad, vagyis az indukciós feltevés miatt vagy mindkét komponens kiszínezhető színnel, vagy legalább az egyik komponensünk egy + 1 csúcsú teljes gráf. Ha színezhető mindkettő színnel, akkor mindkét komponensben különböző színű és , tehát „össze tudjuk illeszteni” a két komponenst és készen vagyunk. Ha pedig az egyik komponensünk egy + 1 pontú teljes gráf, akkor ebben a komponensben -nek és -nak is csak egy szomszédja volt a másik komponensben. Jelöljük ezeket és -vel. Ha most elvesszük mondjuk az és csúcsot az eredeti gráfunkból, akkor ismét két részre esik a gráfunk. Ha ezzel a két ponttal végezzük el az előbbi algoritmust akkor nem kapunk olyan komponenst ami teljes gráf, tehát megkapjuk a gráf egy színnel való jó színezését.
Innentől már csak háromszorosan összefüggő gráfokra kell bizonyítanunk az állítást.
Legyenek ,, olyan csúcsai -nek, hogy és között fut él, és között is fut él, viszont és között nem fut él (mivel nem teljes gráf és összefüggő, ezért ilyen csúcsokat minden esetben találunk). Jelöljük a gráf többi pontját a következőképpen: ,,…, és minden pontnak legyen nagyobb indexű szomszédja is. Ez megtehető: Ha elvesszük a gráfból a és csúcsokat, akkor továbbra is összefüggő marad, hiszen háromszorosan összefüggő volt. Ennek a gráfnak tekintsük egy feszítőfáját. Egy feszítőfának legalább két elsőfokú pontja van, tehát lesz elsőfokú pontja -en kívül. Legyen ez a csúcsunk . Tehát most elvehetjük , , és -at a gráfból és összefüggő marad, és most ennek a gráfnak tekintjük a feszítőfáját, és hasonlóan kapjuk -et stb.
Az utolsó lépésben már csak meg kell adnunk egy megfelelő színezést színnel: Színezzük -et és -ot egyforma színűre. A többi csúcsot indexük szerint sorban színezzük ki mohó módon: -hez mindig találunk majd szabad színt, mert ennek a csúcsnak mindig csak a kisebb indexű szomszédait színeztük még ki és ebből kevesebb van mint . Csak -nek lehet szomszédja, ezek között viszont kettő ( és ) már egyforma színű. Ezzel igazoltuk az állítást.
Brooks, R. L. "On Coloring the Nodes of a Network." Proc. Cambridge Philos. Soc. 37, 194-197, 1941.
Katona, Recski, Szabó "A számítástudomány alapjai." Typotex. Budapest, 2006. p. 80-82.
Matematikaportál
• összefoglaló, színes tartalomajánló lap