グラフ理論の問題
頂点集合 と、次の 本の辺からなる辺集合 をもつ単純無向グラフ を考える。
隣り合う（辺で結ばれた）2 頂点が異なる色になるように の頂点に色を塗るとき、必要な色の数の最小値、すなわち彩色数 を求めよ。
この問題で使うもの
- 頂点彩色と彩色数（説明と入口の問題）
この問題を解けるようになるまで（9 技能）
読み込み中…
右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。
ヒント
行き詰まったら、上から順に 1 つずつ開いてください。
ヒント 1
技能「頂点彩色と彩色数」を使います。実際に少ない色数で塗ってみせる（上からの評価）ことと、それより少ない色では塗れない理由（下からの評価）を合わせましょう。
ヒント 2
このグラフには三角形がないので、クリークによる評価だけでは足りません。長さが奇数の閉路を探してみましょう。奇閉路があれば 2 色では塗れません。
ヒント 3
閉路 は長さ の奇閉路なので です。あとは、例えば に同じ色、 に別の色を塗ることから始めて、残りの頂点 を 3 色目まで使って塗れるか確かめましょう。
答えと解説
答えを見る
どこでつまずきましたか？（選ぶと、戻る場所を案内します）
解説を読む
彩色数は「上からの評価（実際に塗ってみせる）」と「下からの評価（それより少ない色では塗れない理由）」を合わせて求める。
上からの評価：3 色で塗れることを示す。
色を とし、次のように塗る。
すべての辺の両端の色を確かめる。
- : 、: 、:
- : 、: 、:
- : 、: 、:
どの辺も両端の色が異なるので、これは正しい彩色である。よって 。
下からの評価：2 色では塗れないことを示す。
まずクリークを調べると、たとえば頂点 に隣り合う頂点は であるが、この中のどの 2 つも辺で結ばれていないので、 を含む三角形はない。同様に調べると には三角形がなく、 である。したがってクリークからは しか得られない。
そこで奇閉路を使う。 には閉路
があり、その長さは （奇数）である。奇数長の閉路をもつグラフは 2 部グラフではないので、2 色では塗り分けられない（実際、閉路に沿って 2 色を交互に塗ると、5 本目の辺の両端 と が同じ色になってしまう）。よって 。
結論. 上下の評価が一致するので
別解
辺は 1-2, 2-3, 3-4, 4-5, 5-1, 1-6, 6-7, 7-3, 4-6 である。
下界：頂点 1,2,3,4,5 は長さ 5 の奇数長の閉路 1-2-3-4-5-1 をなす。奇数長の閉路は 2 色では塗れないので、。
上界：3 色 A, B, C で次のように塗る。
1=A, 2=C, 3=B, 4=A, 5=B, 6=B, 7=A。
各辺を確かめる。
1-2: A,C
2-3: C,B
3-4: B,A
4-5: A,B
5-1: B,A
1-6: A,B
6-7: B,A
7-3: A,B
4-6: A,B
どの辺の両端も異なる色なので、3 色で塗れる。
よって 。