Brooks-tétel

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.

A gráfelméletben a Brooks-tétel a gráf maximális fokszáma és kromatikus száma közötti összefüggés. A tétel Rowland Leonard Brooks-tól származik, aki 1941-ben publikálta On Coloring the Nodes of a Network cikkében.

Legyen $G$ véges, összefüggő gráf, ami nem teljes gráf vagy páratlan csúcsú körgráf. Jelölje $\Delta (G)$ a $G$ maximális fokszámát, $\chi (G)$ pedig a kromatikus számát. Ekkor

$\chi (G)\leq \Delta (G).$

Bizonyítás

$\Delta (G)$ = 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 $\Delta (G)$ $\geq$ 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 $x$ 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 $x$-et, és nevezzük ezeket a komponenseket $G_{1}$ és $G_{2}$-nek. Ha több mint két komponensre esik szét, akkor maradjon $G_{1}$ továbbra is egy komponens és $G_{2}$ meg legyen az összes többi komponens és x uniója: $G_{2}$ = ($G$ \ $G_{1}$) $\cup$ {$x$}. 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 $\Delta (G)$, viszont $x$ foka feltétlenül kisebb lesz mindkét komponensben $\Delta (G)$-nél. Ebből következik, hogy egyik komponens sem lehet $\Delta (G)$ + 1 pontú teljes gráf. Tehát, az indukciós feltevésünk miatt, mindkét komponens kiszínezhető $\Delta (G)$ színnel, és ha $x$-et mindkét komponensben ugyanolyan színűre választjuk, akkor ha újra „összerakjuk” a gráfot akkor az eredeti gráfunknak egy $\Delta (G)$ 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 $x$ és $y$ pont elhagyásával szétesik a gráfunk $G_{1}$ és $G_{2}$-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 $x$ és $y$ egyforma színű, és a másik komponens minden színezésénél $x$ és $y$ különböző színű. Ebben az esetben nem tudjuk újra „összerakni” a gráfunkat. Ebben az esetben tekintsük a $G_{1}$ és $G_{2}$ komponenst és mindkettőben húzzunk be $x$ és $y$ között egy élt. Így $x$ és $y$ fokszáma továbbra is legfeljebb $\Delta (G)$ marad, vagyis az indukciós feltevés miatt vagy mindkét komponens kiszínezhető $\Delta (G)$ színnel, vagy legalább az egyik komponensünk egy $\Delta (G)$ + 1 csúcsú teljes gráf. Ha színezhető mindkettő $\Delta (G)$ színnel, akkor mindkét komponensben különböző színű $x$ és $y$, tehát „össze tudjuk illeszteni” a két komponenst és készen vagyunk. Ha pedig az egyik komponensünk egy $\Delta (G)$ + 1 pontú teljes gráf, akkor ebben a komponensben $x$-nek és $y$-nak is csak egy szomszédja volt a másik komponensben. Jelöljük ezeket $x'$ és $y'$-vel. Ha most elvesszük mondjuk az $x$ és $y'$ 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 $\Delta (G)$ 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 $v_{1}$,$v_{2}$,$v_{n}$ olyan csúcsai $G$-nek, hogy $v_{1}$ és $v_{n}$ között fut él, $v_{2}$ és $v_{n}$ között is fut él, viszont $v_{1}$ és $v_{2}$ között nem fut él (mivel $G$ 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: $v_{3}$,$v_{4}$,…,$v_{n-1}$ és minden pontnak legyen nagyobb indexű szomszédja is. Ez megtehető: Ha elvesszük a gráfból a $v_{1}$ és $v_{2}$ csúcsokat, akkor $G$ 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 $v_{n}$-en kívül. Legyen ez a csúcsunk $v_{3}$. Tehát most elvehetjük $v_{1}$, $v_{2}$, és $v_{3}$-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 $v_{4}$-et stb.

Az utolsó lépésben már csak meg kell adnunk egy megfelelő színezést $\Delta (G)$ színnel: Színezzük $v_{1}$-et és $v_{2}$-ot egyforma színűre. A többi csúcsot indexük szerint sorban színezzük ki mohó módon: $v_{i}$-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 $\Delta (G)$. Csak $v_{n}$-nek lehet $\Delta (G)$ szomszédja, ezek között viszont kettő ($v_{1}$ és $v_{2}$) már egyforma színű. Ezzel igazoltuk az állítást.

Hivatkozások

• 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.