グラフ理論の問題
頂点集合 と、次の 本の辺からなる辺集合 をもつ単純無向グラフ を考える。
隣り合う（辺で結ばれた）2 頂点が異なる色になるように の頂点を塗り分けるとき、必要な色の数の最小値、すなわち彩色数 を求めよ。
この問題で使うもの
- 頂点彩色と彩色数（説明と入口の問題）
この問題を解けるようになるまで（9 技能）
読み込み中…
右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。
ヒント
行き詰まったら、上から順に 1 つずつ開いてください。
ヒント 1
技能「頂点彩色と彩色数」を使う。彩色数は、実際の塗り分け（上からの評価）と、それより少ない色では塗れない理由（下からの評価）を合わせて決める。
ヒント 2
下からの評価には、どの 2 頂点も隣り合う頂点の組（クリーク）を探すとよい。 が成り立つ。
ヒント 3
頂点 は三角形をなすので 。あとは頂点 の順に、隣と重ならない色を 3 色の中から選んで塗り分けられるか確かめる。
答えと解説
答えを見る
どこでつまずきましたか？（選ぶと、戻る場所を案内します）
解説を読む
彩色数は「上からの評価（実際に塗り分けを作る）」と「下からの評価（それより少ない色では塗れない理由）」を合わせて求める。
下からの評価. 頂点 について、辺 がすべてあるので、 は大きさ のクリーク（三角形）である。三角形の 3 頂点はどの 2 つも隣り合うので、すべて異なる色が必要である。よって
上からの評価. 3 色 で実際に塗り分けを作る。番号の小さい頂点から順に、隣の頂点と重ならない色を選ぶ。
- 頂点 :
- 頂点 （隣は ）:
- 頂点 （隣は ）:
- 頂点 （隣は で色 ）:
- 頂点 （隣は で色 ）:
- 頂点 （隣は で色 ）:
本の辺の両端の色を確かめると、、、、、、、、、、 で、どの辺も両端が異なる色である。よって 。
結論. より 。
別解
G には三角形 {1,2,3} があるので、少なくとも 3 色が必要で 。
3 色で塗れるか確かめる。
頂点 1=A, 2=B, 3=C とする。
- 辺 {2,4},{3,4} より、頂点 4 は 2 と 3 の両方と異なる色なので 4=A。
- 辺 {3,5},{4,5} より、頂点 5 は 3(C) と 4(A) と異なる色なので 5=B。
- 頂点 6 は 4(A), 5(B), 1(A) と隣り合う。4 と 1 は A、5 は B なので、6=C とできる。
全辺を確認する。
{1,2}: A-B 可、{1,3}: A-C 可、{2,3}: B-C 可、{2,4}: B-A 可、{3,4}: C-A 可、{3,5}: C-B 可、{4,5}: A-B 可、{4,6}: A-C 可、{5,6}: B-C 可、{1,6}: A-C 可。
すべて異なる色なので 3 色で塗れる。
よって 。