Brook's theorem. Where I make a mistake?

76 Views Asked by At

please explain me one thing: According to Brook's theorem $ \chi(G ) \le \deg(u) $ But it can't be true. After all, there are $\deg(u) + 1 $ colors and I'm enclosing a draw.

https://i.stack.imgur.com/mmw6K.png

$\deg(u) = 5 $ and there are six colors, and graph isn't complet and it not odd-cycle. I don't understand.

What mistake I do?

1

There are 1 best solutions below

0
On BEST ANSWER

The chromatic number of a graph isn't defined from any colouring you want, but from the optimal colouring. Your graph can be coloured using only two colours (one for vertex $u$ and one for all the rest). Therefore $\chi(G) = 2$, and the theorem still holds.