To see that the construction increases the chromatic number formula_1, consider a proper "k"-coloring of formula_2; that is, a mapping formula_3 with formula_4 for adjacent vertices "x","y". If we had formula_5 for all "i", then we could define a proper ("k"−1)-coloring of "G" by formula_6 when formula_7, and formula_8 otherwise. But this is impossible for formula_1, so "c" must use all "k" colors for formula_10, and any proper coloring of the last vertex "w" must use an extra color. That is, formula_11.