ここで，Knの方の頂点に1,2,3,...,nと番号を振り， グラフGの方の各頂点vに対して，f(v)の数字を割り振ってみよう．
Gにおいて辺で結ばれている2頂点は，fが準同型であるため，Knにおいて辺で結ばれた2頂点に写される．したがって，このように番号付けを行なうと，Gの各頂点に対して，辺で隣接する2頂点が異なる番号になるように番号付けを与えることができることになる． このような番号付けは，グラフGのn-彩色と呼ばれる．(番号nをn番目の色と考える．番号付けできることをn-彩色可能であるという． n-彩色可能であるような最小のnをGの彩色数といい，χ(G)と表記する．)
つまり，グラフGからKnへの準同型があるとき，必ずグラフGにはn-彩色が存在する，ということである．
逆に，グラフGにn彩色があれば，必ずグラフGからKnへの準同型が存在することも簡単に分かる．なぜなら，Gのn彩色が与えられているとき，Gの頂点vの行き先を，vに与えられた色の番号を持つKnの頂点とすれば準同型の条件が自動的に満たされるためである．
|
性質： グラフGからKnへの準同型が存在することは，グラフGがn-彩色可能であることと等価である． |
この意味で，グラフの準同型をグラフの彩色の一般化と見ることもできる． グラフHが与えられているとき，グラフGがHへの準同型を持つことを，グラフGはH-彩色可能である，という．
この例のH-彩色では，2に辺で隣接する頂点は1だけが彩色可能(3はだめ)，というように，各色ごとに隣接する頂点に塗れる色の種類が限定されることになる． (n-彩色の場合には，隣接頂点には自分以外の色がすべて使える．)