Let G be a graph with n vertices. Prove that the chromatic number of G is greater than or equal to its clique number. Also prove that the chromatic number is greater than or equal to (n/the adjacency number of G).
I know that in a clique any 2 vertices are adjacent, and that in a clique of 4 each vertex has a degree 3, so that we would need four different colors. So assuming a clique has n vertices we need n colors, so the clique number cannot be greater than the chromatic number, so it has to be less than or equal. Is that an adequate way to prove the first part?
For the second part, I am utterly confused about where to start this proof.
Best Answer
Your first proof looks good, but it can be stated more simply. If a graph contains a clique of size $k$, then at least $k$ colors are required to color just the clique. Thus, the chromatic number is at least $k$.
For the second part, work by contradiction. If you could color the graph $G$ with fewer than $n / \alpha(G)$ colors, then one of your color classes has size strictly larger than $\alpha(G)$ (why?). Since no two vertices within a color class are adjacent, that color class is itself an independent set of size strictly larger than $\alpha(G)$ - a contradiction.