Proper $n$-coloring of a graph clarification

87 Views Asked by At

There exists a theorem that states:

Let G be a planar graph. There exists a proper 6-coloring of G.

Any single-vertex graph $T$ is a planar graph. However, $T$ surely cannot be colored using all six colors in any six-color set.

Is it then correct to conclude that a proper $n$-coloring only requires that at most $n$ colors are used?

1

There are 1 best solutions below

0
On BEST ANSWER

Yes. One is not required to use all $k$ colors in a $k$-coloring of a graph.