グラフ理論の問題

彩色数は「下からの評価」と「上からの評価」を一致させて求める。

下からの評価（クリーク）
頂点 $1,2,3,4$ について、$6$ 本の辺 $\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},\{3,4\}$ がすべて $E$ に含まれる。したがって $\{1,2,3,4\}$ は大きさ $4$ のクリーク（$K_4$）である。この $4$ 頂点はどの 2 つも隣り合うので、すべて異なる色にする必要がある。よって
$$\chi (G)\ge \omega (G)\ge 4.$$

上からの評価（彩色の構成）
色を $\text{A},\text{B},\text{C},\text{D}$ とし、次のように塗る。
- $1:\text{A},2:\text{B},3:\text{C},4:\text{D}$
- 頂点 $5$ の隣接頂点は $4,6,7$ である。$4$ が $\text{D}$ なので $5:\text{A}$ とする（$5$ と $1$ は隣り合わない）。
- 頂点 $7$ の隣接頂点は $1,5,6$ である。$1,5$ が $\text{A}$ なので $7:\text{B}$ とする。
- 頂点 $6$ の隣接頂点は $5,7$ である。$5:\text{A}$、$7:\text{B}$ なので $6:\text{C}$ とする。

$11$ 本の辺の両端の色を確かめる。
- $\{1,2\}$: A,B
- $\{1,3\}$: A,C
- $\{1,4\}$: A,D
- $\{2,3\}$: B,C
- $\{2,4\}$: B,D
- $\{3,4\}$: C,D
- $\{4,5\}$: D,A
- $\{5,6\}$: A,C
- $\{5,7\}$: A,B
- $\{6,7\}$: C,B
- $\{1,7\}$: A,B

どの辺も両端の色が異なるので、これは $4$ 色による正しい彩色である。よって $\chi (G)\le 4$ である。

まとめ
$4\le \chi (G)\le 4$ より、$\chi (G)=4$ である。

頂点 1,2,3,4 の間には 6 本の辺 {1,2},{1,3},{1,4},{2,3},{2,4},{3,4} がすべてあるので、これは完全グラフ $K_4$ である。$K_4$ の 4 頂点は互いに隣り合うので、すべて異なる色が必要であり、$\chi (G)\ge 4$ である。

次に 4 色で塗れることを示す。色を 1,2,3,4 とする。
- 頂点 1→色1、2→色2、3→色3、4→色4 とする。
- 頂点 5 は 4 とだけ隣り合う（この時点で塗られている隣接頂点は 4 のみ）ので、色1 とする。
- 頂点 7 は 1（色1）と 5（色1）に隣り合うので、色2 とする。
- 頂点 6 は 5（色1）と 7（色2）に隣り合うので、色3 とする。

辺をすべて確認する。
{1,2}: 1,2 / {1,3}: 1,3 / {1,4}: 1,4 / {2,3}: 2,3 / {2,4}: 2,4 / {3,4}: 3,4 / {4,5}: 4,1 / {5,6}: 1,3 / {5,7}: 1,2 / {6,7}: 3,2 / {1,7}: 1,2。
どの辺も端点の色が異なるので、正しい彩色である。

よって $\chi (G)=4$ である。