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

  • $\begingroup$ In 1 and 2, are the colorings supposed to be proper colorings, i.e., adjacent vertices have different colors? $\endgroup$
    – bof
    Jun 17, 2018 at 23:35
  • $\begingroup$ Is $\lambda(G)$ the chromatic number of $G$? If so, why do you use $\lambda$ instead of the usual $\chi$? $\endgroup$
    – bof
    Jun 17, 2018 at 23:44
  • $\begingroup$ Why do you not reply to comments? $\endgroup$
    – bof
    Jun 19, 2018 at 1:09
  • $\begingroup$ @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 $\endgroup$
    – XPenguen
    Jun 19, 2018 at 1:30
  • $\begingroup$ @bof You can repost your answer again If you don't think there is anything wrong with it. I was going to accept your answer, it's just that I hadn't checked the site the last couple of days. $\endgroup$
    – XPenguen
    Jun 19, 2018 at 1:35

1 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.


You must log in to answer this question.

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