Brooks-tétel

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.^[1]

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

${\displaystyle \chi (G)\leq \Delta (G).}$

Bizonyítás

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

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

Források