Question

Graph Theory, discrete math question:

Let G be a graph with 100 vertices, and chromatic number 99. Prove a lower bound for the clique number of G. Any lower bound will do, but try to make it as large as you can.

Please follow this hint my professor gave and show your work, Thank you!!

Hint: can you prove that the clique number is at least 1? Now how about 2? Can you prove that the clique number must be at least 2? In other words, can you prove that the graph has a K2 subgraph? Almost certainly, you can. Now try to prove that G has a K3 subgraph (thereby proving that the clique number is at least 3). Go up as high as you can. For even more challenge, once you reached a number that you think is best possible, try to prove that it is best possible. I.e. find a graph on 100 vertices with chromatic number 99 whose clique number exactly matches your bound.

Answer 1