1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ actually the theorem states that even $4$ colors are enough. $\endgroup$
    – Denis
    Commented Dec 8, 2014 at 16:36
  • $\begingroup$ There are theorems for 4, 5 and 6 colors. $\endgroup$ Commented Dec 8, 2014 at 19:42

1 Answer 1

1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .