Discrete math, graph theory question:
Let G be a graph with 100 vertices, and chromatic number 99.
Prove a lower bound for the clique number of G. (Hint: Any lower bound will do, but try to make it as large as you can.)
Since chromatic number is 99, let be the colours used. Then there exists a vertex which is coloured and it must have at least 98 neighbours each coloured differently from , otherwise we could use lesser than 99 colours to colour the graph. Now when will 98 neighbours of be coloured each with different colour? Only when together with its 98 neighbours form a clique. Hence, there must exist a clique of size 99 and lower bound for the clique number is 99.
Get Answers For Free
Most questions answered within 1 hours.