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

Question

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

Answer 1

Call the given coloring with at least two vertices of each color a friendly coloring.

Now start with the coloring that uses the minimal number of colors. If every color is used twice we are done. If not, pick a vertex with a lonely color, look up the vertices that share its color in the friendly coloring and repaint them with the lonely color. Repeat as long as there are lonely vertices.

It is clear that this always gives an admissible coloring and that it does not increase the number of colors. But the procedure must stop because a repainted vertex will not be repainted again. So we end up with a friendly minimal coloring.