Recall the definition of a complete graph K_n is a graph with n vertices such th
ID: 3808218 • Letter: R
Question
Recall the definition of a complete graph K_n is a graph with n vertices such that every vertex is connected to every oilier 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.Explanation / Answer
We 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 require n colors, so the clique number cannot be bigger than the chromatic number, so it has to be less than or equal.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.