Brook-tétel

1. Sablon:Label A **Brook-tétel** a gráf színezésére vonatkozik, és azt mondja ki:

Tétel:

Egy összefüggő gráf kromatikus száma ($\chi (G)$) legfeljebb megegyezik a gráf maximális fokszámával ($\mathrm{\Delta }$), kivéve két esetet:

1. A gráf teljes gráf ($K_n$), ahol minden csúcs szomszédos minden más csúccsal ($\chi (G)=n=\mathrm{\Delta }+1$).
2. A gráf páratlan kör ($C_{2k+1}$), ahol $\chi (G)=3=\mathrm{\Delta }+1$.

Általános formula:

$$\chi (G)\le \mathrm{\Delta },\text{ha }G\text{ nem teljes gráf és nem páratlan kör.}$$

---

Brook-tétel bizonyítása

A bizonyítás a **greedy (kapzsi) színezés** módszerén alapszik, amely szerint a csúcsokat egy adott sorrendben színezzük, és mindig a legkisebb lehetséges színt választjuk, amely nem ütközik az adott csúcs szomszédaival.

1. Előzetes feltételek

• Tekintsünk egy gráfot $G=(V,E)$, ahol a maximális fokszám $\mathrm{\Delta }$.
• Ha $G$ nem összefüggő, akkor az összefüggő komponenseket külön-külön színezzük, így a bizonyítás minden komponensre igaz.

2. Speciális esetek

• Teljes gráf ($K_n$):

Minden csúcs szomszédos minden más csúccsal, ezért minden csúcsnak külön színt kell adni. Így: $$\chi (K_n)=n=\mathrm{\Delta }+1$$

• Páratlan kör ($C_{2k+1}$):

Egy páratlan körben minden csúcs fokszáma $\mathrm{\Delta }=2$, de legalább 3 szín szükséges a színezéshez (például $C_5$ esetén): $$\chi (G)=\mathrm{\Delta }+1=3$$

3. Általános gráfokra (nem teljes gráf és nem páratlan kör):

A cél annak igazolása, hogy egy ilyen gráf színezéséhez legfeljebb $\mathrm{\Delta }$ szín elegendő.

1. Greedy algoritmus:

Rendezzük a gráf csúcsait egy adott sorrendbe ($v_1,v_2,\dots ,v_n$). Ezt a sorrendet úgy állítjuk elő, hogy a gráf maradjon összefüggő, és minden csúcsnak legfeljebb $\mathrm{\Delta }$ szomszédja legyen.

1. Színezési lépések:

Haladjunk végig a csúcsokon a sorrendben, és minden $v_i$-hez rendeljen egy olyan színt, amely különbözik a $v_i$ szomszédainak színeitől: $$\text{Szín}(v_i)=\min \{1,2,\dots ,\mathrm{\Delta }\}\setminus \text{Szomszédok}(v_i)$$ Mivel egy csúcsnak legfeljebb $\mathrm{\Delta }$ szomszédja lehet, mindig van legalább egy szabad szín.

1. Kivételes esetek kezelése:

Ha $G$ nem teljes gráf és nem páratlan kör, akkor mindig létezik olyan sorrend, amely biztosítja, hogy a színezéshez $\mathrm{\Delta }$ szín elegendő legyen.

4. Technikai megjegyzések

• Az algoritmus feltételezi, hogy $G$ nem teljes gráf ($K_n$) és nem páratlan kör ($C_{2k+1}$).
• Az eliminációs sorrend előállítását az összefüggőség biztosítja: mindig található olyan csúcs, amelynek eltávolítása után a gráf továbbra is összefüggő marad.

---

Összegzés

A Brook-tétel bizonyítása azon alapul, hogy a gráf csúcsait megfelelő sorrendben választva a greedy algoritmus garantálja a $\mathrm{\Delta }$-színezést. Az egyetlen kivétel a teljes gráfok ($K_n$) és a páratlan körök ($C_{2k+1}$), ahol $\chi (G)=\mathrm{\Delta }+1$.