5 What is the minimum number of colors that are needed to co

(5) What is the minimum number of colors that are needed to color the vertices of a K₄ graph such that no adjacent vertices have the same color? Why?

(6) a. Is a K₂ a tree?

            b. If n ³ 3, is a K_na tree? Give a proof to support your answer.

Solution

5 - The minimum number of colors that are needed to color the vertices of a K4 graph such that no adjacent vertices have the same color is 4, since each vertex is adjacent to remaining (n – 1) vertices. Therefore, each vertex requires a new color. Hence the chromatic number of K_n = n.

6- Is a K2 a tree?- Yes

b - If n ³ 3, is a Kna tree? Yes