グラフ理論の問題

頂点集合を $V=\{0,1,2,\dots ,8\}$ とし、相異なる 2 頂点 $i,j$ を、$j-i\not\equiv \pm 1(\mathrm{mod}9)$ のときに限り辺で結んだ単純グラフを $G$ とする（$G$ は長さ $9$ の閉路 $C_9$ の補グラフである）。

$G$ の彩色数（隣り合う頂点が異なる色になるように頂点を塗るのに必要な色の数の最小値）を $\chi (G)$、辺彩色数（端点を共有する辺が異なる色になるように辺を塗るのに必要な色の数の最小値）を ${\chi }^{\prime }(G)$ とする。組 $(\chi (G),{\chi }^{\prime }(G))$ をこの順に求めよ。

頂点集合 $V=\{0,1,2,3,4,5,6,7\}$ と、次の $14$ 本の辺からなる辺集合 $E$ をもつ単純無向グラフ $G=(V,E)$（車輪グラフ）を考える。
$$\{0,1\},\{0,2\},\{0,3\},\{0,4\},\{0,5\},\{0,6\},\{0,7\},$$
$$\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{5,6\},\{6,7\},\{7,1\}$$
$G$ の彩色数 $\chi (G)$（隣接する 2 頂点が異なる色になるように頂点を塗るときの色の数の最小値）と、辺彩色数 ${\chi }^{\prime }(G)$（端点を共有する 2 辺が異なる色になるように辺を塗るときの色の数の最小値）を、組 $(\chi (G),{\chi }^{\prime }(G))$ の形でこの順に求めよ。

$n\ge 5$ を整数とする。頂点集合を $V_n=\{0,1,2,\dots ,n-1\}$ とし、相異なる 2 頂点 $i,j$ を
$$j-i\equiv \pm 1\text{または}j-i\equiv \pm 2(\mathrm{mod}n)$$
のときに限り辺で結んだ単純無向グラフを $G_n$ とする（閉路 $C_n$ の 2 乗グラフ）。$G_n$ の彩色数（隣接する頂点が異なる色になるように頂点を塗るのに必要な最小の色数）を $\chi (G_n)$、辺彩色数（同じ頂点を端点にもつ辺が異なる色になるように辺を塗るのに必要な最小の色数）を ${\chi }^{\prime }(G_n)$ とする。
$$S=\sum _{n=5}^{12}(\chi (G_n)+{\chi }^{\prime }(G_n))$$
の値を求めよ。

頂点集合を $V=\{2,3,4,\dots ,12\}$（$11$ 個の頂点）とし、相異なる 2 頂点 $i<j$ を、$i$ が $j$ を割り切るときに限り辺で結んだ単純無向グラフを $G$ とする。すなわち $G$ の辺は次の $12$ 本である。
$$\{2,4\},\{2,6\},\{2,8\},\{2,10\},\{2,12\},\{3,6\},\{3,9\},\{3,12\},\{4,8\},\{4,12\},\{5,10\},\{6,12\}$$
$G$ の最大マッチングの辺数を $\nu (G)$、最大独立集合の頂点数を $\alpha (G)$、最小頂点被覆の頂点数を $\tau (G)$ とする。$\nu (G),\alpha (G),\tau (G)$ をこの順に組 $(\nu (G),\alpha (G),\tau (G))$ として求めよ。

$G=(V,E)$ を頂点数が $1$ 以上の有限な単純無向グラフとする。$G$ の頂点彩色数（隣接する 2 頂点が異なる色になるように頂点を塗り分けるのに必要な色の最小数）を $\chi (G)$ と書き、$k=\chi (G)$ とおく。頂点 $v$ の次数（$v$ に隣接する頂点の個数）を $\mathrm{deg}v$ と書く。

このとき、$G$ には $\mathrm{deg}v\ge k-1$ を満たす頂点 $v$ が少なくとも $k$ 個存在することを証明せよ。