Understanding CLIQUE structure

Question

I am working on the following problem:

Recall the definition of a complete graph Kn is a graph with n vertices such that every vertex is connected to every other vertex. Recall also that a clique is a complete subset of some graph. The graph coloring problem consists of assigning a color to each of the vertices of a graph such that adjacent vertices have different colors and the total number of colors used is minimized. We define the chromatic number of a graph G to be this minimum number of colors required to color graph G. Prove that the chromatic number of a graph G is no less than the size of a maximal clique of G.

So far, I have been thinking about the problem and came up with the following:

• In a clique, every vertex is adjacent to every other vertex
• Therefore, since the problem states adjacent verteces always have different colors, the number of colors needed would be the number of verteces in the clique
• Thus, the chromatic number of any graph G has to be at least the maximal size of the clique, per the definition of a clique.

Can someone verify if my understanding is correct? Or am I glaringly not understanding a clique?

Answer 1

Your understanding is right. So in particular, for any graph $G$ with a clique of size $k$, you will need at least $k$ colors to properly color it. In case this is not obvious, you can think about it via a contradiction. So assume $G$ contains a clique of size $k$, and you have a proper coloring with less than $k$ colors. It follows that the clique contains at least two vertices with the same color. By definition of a clique, these two vertices are adjacent. But this is a contradiction to the coloring being proper.

Further, one might also wonder if the chromatic number of a graph would always equal the clique number. In this direction, you can have a look at perfect graphs for which the chromatic number of every induced subgraph equals its clique number. On the other hand, the Mycielski graphs show that there are graph that don't even contain a triangle (equivalently, a clique on 3 vertices), while the chromatic number can be arbitrarily large.