グラフ理論の問題

彩色数. 頂点 $1,2,\dots ,7$ は長さ $7$ の閉路 $1-2-3-4-5-6-7-1$ をなす。奇数の長さの閉路は 2 色では塗れない（2 色で交互に塗ると、1 周して戻ったとき頂点 $7$ と $1$ が同じ色になる）ので、閉路だけで $3$ 色以上必要である。さらに頂点 $0$ は $1,\dots ,7$ のすべてと隣接するので、閉路に使った色とは異なる色が必要になる。よって $\chi (G)\ge 4$。

一方、頂点 $0$ を色 $4$、頂点 $1,2,3,4,5,6,7$ を順に色 $1,2,1,2,1,2,3$ で塗ると、隣接する頂点はすべて異なる色になる。よって $\chi (G)=4$。

辺彩色数. 頂点 $0$ の次数は $7$ で、頂点 $0$ に接続する $7$ 本の辺は互いに端点を共有するので、すべて異なる色が必要である。よって ${\chi }^{\prime }(G)\ge 7$。

色を $1,2,\dots ,7$ とし、添字は $7$ を法として $1\sim 7$ で考える（例: $8$ は $1$、$9$ は $2$ とみなす）。
- 辺 $\{0,i\}$ に色 $i$（$i=1,\dots ,7$）
- 辺 $\{i,i+1\}$ に色 $i+3$（$i=1,\dots ,7$。$\{7,8\}$ は $\{7,1\}$ を表す）

と塗る。具体的には $\{1,2\}:4,\{2,3\}:5,\{3,4\}:6,\{4,5\}:7,\{5,6\}:1,\{6,7\}:2,\{7,1\}:3$ である。

頂点 $0$ では色 $1,\dots ,7$ がすべて異なる。頂点 $i$（$1\le i\le 7$）に接続する辺は $\{0,i\}$（色 $i$）、$\{i-1,i\}$（色 $i+2$）、$\{i,i+1\}$（色 $i+3$）の 3 本で、$i,i+2,i+3$ は $7$ を法として相異なる。よってこれは $7$ 色での正しい辺彩色であり、${\chi }^{\prime }(G)=7$。

以上より、$(\chi (G),{\chi }^{\prime }(G))=(4,7)$ である。

$G$ は中心 0 と外周の 7 サイクル $1-2-3-4-5-6-7-1$ からなる車輪グラフ $W_7$ である。

点彩色: 外周は奇サイクル $C_7$ なので 2 色では塗れず 3 色が必要。中心 0 は外周の全頂点と隣接するので、外周と異なる色が必要で、合計 4 色以上。逆に、外周を 1,2,1,2,1,2,3 の 3 色で塗り（7 本の辺はいずれも隣り合う色が異なる）、0 を 4 色目にすれば 4 色で塗れる。よって $\chi (G)=4$。

辺彩色: 中心 0 の次数は 7 で最大次数 $\Delta =7$ なので ${\chi }^{\prime }(G)\ge 7$。7 色で塗れることを示す。外周の頂点 $k$ ($1\le k\le 7$) について、スポーク $\{0,k\}$ を色 $k$ とし、外周の辺 $\{k,k+1\}$（添字は 7 を法として 1〜7）を色 $k+3$ とする（色も 7 を法として 1〜7）。
頂点 0: スポークの色は $1,\dots ,7$ で全て異なる。
頂点 $k$: スポーク $k$、辺 $\{k,k+1\}$ は色 $k+3$、辺 $\{k-1,k\}$ は色 $k+2$。3 色 $k,k+3,k+2$ は 7 を法として異なる。
よって正当な 7 辺彩色が得られ、${\chi }^{\prime }(G)=7$。

答え: $(4,7)$。