# vertex coloring of a graph $G$ such that colors appear twice

1. Let $G=(V,E)$ be a graph whose vertices can be colored with $m$-colors, such that each color appears at least twice.

2. Let $\lambda(G)$ denote the minimum number of colors needed for a vertex-coloring of $G$

Use 1. to prove that such a coloring can be achieved with $\lambda(G)$ colors

Let $\alpha$ denote a coloring with property 1. and $\beta$ a coloring with $\lambda(G)$ colors. $\beta$ has a color class with only one vertex if $\beta$ doesn't have property 1.

I don't know how that helps to prove that such a coloring can be achieved with $\lambda(G)$ colors

Edit: A coloring of the graph $G$ is a proper coloring. $u,v$ have different colors if $(u,v)\in E$

Would appreciate any help

• In 1 and 2, are the colorings supposed to be proper colorings, i.e., adjacent vertices have different colors?
– bof
Jun 17, 2018 at 23:35
• Is $\lambda(G)$ the chromatic number of $G$? If so, why do you use $\lambda$ instead of the usual $\chi$?
– bof
Jun 17, 2018 at 23:44
• @bof Sry, you're right. The vertex coloring is supposed to be a proper coloring and I used $\lambda$ because the script I am learning from used it as well Jun 19, 2018 at 1:30