グラフ理論の問題

頂点集合を $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))$ をこの順に求めよ。

$K_{4,4}$ を、$4$ 個の頂点からなる部集合 $A$ と $4$ 個の頂点からなる部集合 $B$ をもつ完全二部グラフ（$A$ の各頂点と $B$ の各頂点がちょうど 1 本の辺で結ばれ、それ以外に辺はない単純グラフ）とする。

$K_{4,4}$ を平面に描く。ただし、頂点は相異なる点、辺はその両端点を結ぶ連続曲線で表し、辺は自分の端点以外の頂点を通らず、2 本の辺は有限個の点でしか交わらず、3 本以上の辺が同じ 1 点（端点以外）で交わることはないものとする。このような描き方において、2 本の辺が端点以外で交わる点の個数を交差数とよぶ（同じ 2 本の辺が何点で交わっても、交わる点を 1 点ずつ数える）。

$K_{4,4}$ のすべての描き方にわたる交差数の最小値を求めよ。

頂点集合を $V=\{0,1,2,3,4,5,6\}$ とし、相異なる 2 頂点 $i,j$ を、$i-j$ を $7$ で割った余りが $2,3,4,5$ のいずれかであるときに限り辺で結んだ単純無向グラフを $G$ とする。言い換えると、$i,j$ が辺で結ばれるのは $i-j\equiv \pm 2$ または $i-j\equiv \pm 3(\mathrm{mod}7)$ のときに限る。$G$ の彩色数 $\chi (G)$（隣接する頂点が異なる色になるように頂点を塗るのに必要な色の最小数）と、辺彩色数 ${\chi }^{\prime }(G)$（端点を共有する辺が異なる色になるように辺を塗るのに必要な色の最小数）を、この順に組 $(\chi (G),{\chi }^{\prime }(G))$ で答えよ。

頂点集合を $V=\{(i,j)\mid i\in \{1,2,3,4\},j\in \{1,2,3,4,5\}\}$ とし、相異なる 2 頂点 $(i,j),(i^{\prime },j^{\prime })$ を $|i-i^{\prime }|+|j-j^{\prime }|=1$ のときに限り辺で結んだ単純無向グラフを $G$ とする（$4$ 行 $5$ 列の格子グラフ）。各辺の長さを $1$ とする。

$G$ のある頂点から出発して $G$ の辺をたどり、出発した頂点に戻ってくる閉じた歩道で、$G$ のすべての辺を少なくとも 1 回ずつ通るものを考える（同じ辺や同じ頂点を何度通ってもよい）。このような閉じた歩道の長さ（通った辺の本数を、重複も含めて数えたもの）の最小値を求めよ。

集合 $[7]=\{1,2,3,4,5,6,7\}$ の 3 元部分集合全体を頂点集合とし、2 つの頂点（3 元部分集合）$A,B$ を $A\cap B=\varnothing$ のときに限り辺で結んだ単純グラフ（クネーザーグラフ $K(7,3)$）を $G$ とする。$G$ の彩色数 $\chi (G)$ と辺彩色数 ${\chi }^{\prime }(G)$ をこの順に求めよ。