グラフ理論の問題

方針 頂点 $1$ から順に、隣り合う頂点に交互に色を付けていく（2 色塗り分け）。途中で矛盾（同じ色どうしが辺で結ばれる）が起きなければ 2 部グラフであり、起きれば奇数長の閉路が見つかる。

手順 1（頂点 $1$ の色を決める） 頂点 $1$ を白とする。

手順 2（$1$ の隣を塗る） 頂点 $1$ に隣接するのは $2,6$ なので、$2,6$ を黒とする。

手順 3（その隣を塗る） 黒の頂点 $2$ に隣接するのは $1,3,7$、黒の頂点 $6$ に隣接するのは $5,1$。まだ色のない $3,7,5$ を白とする。

手順 4（さらにその隣を塗る） 白の頂点 $3$ に隣接するのは $2,4,8$、白の頂点 $5$ に隣接するのは $4,6,8$、白の頂点 $7$ に隣接するのは $2,8$。まだ色のない $4,8$ を黒とする。

これで全頂点に色が付いた：
$$\text{白}:\{1,3,5,7\},\text{黒}:\{2,4,6,8\}.$$

手順 5（すべての辺を確認） $10$ 本の辺の両端の色を調べると
$\{1,2\}$：白・黒、$\{2,3\}$：黒・白、$\{3,4\}$：白・黒、$\{4,5\}$：黒・白、$\{5,6\}$：白・黒、$\{6,1\}$：黒・白、$\{2,7\}$：黒・白、$\{7,8\}$：白・黒、$\{8,5\}$：黒・白、$\{3,8\}$：白・黒
となり、どの辺も両端の色が異なる。よって $G$ は 2 部グラフである。「2 部グラフ $⟺$ 奇数長の閉路をもたない」により、$G$ の閉路はすべて偶数長である（例えば $1\text{-}2\text{-}3\text{-}4\text{-}5\text{-}6\text{-}1$ は長さ $6$、$3\text{-}4\text{-}5\text{-}8\text{-}3$ は長さ $4$）。

手順 6（答えが一意であること） $G$ は連結なので、頂点 $1$ の色を決めると、上の手順で他のすべての頂点の色が強制的に決まる。したがって頂点 $1$ と同じ色の頂点の集合は塗り方によらず一通りに定まり、
$$\{1,3,5,7\}$$
である。

頂点 $1$ を白とし、辺でつながる頂点を順に反対色で塗っていく。

• $1$ の隣接頂点 $2,6$ は黒。
• $2$ の隣接頂点 $3,7$ は白。
• $6$ の隣接頂点 $5$ は白。
• $3$ の隣接頂点 $4,8$ は黒。

これで白は $\{1,3,5,7\}$、黒は $\{2,4,6,8\}$ となる。

10 本の辺をすべて確かめる。
- $\{1,2\}$: 白–黒
- $\{2,3\}$: 黒–白
- $\{3,4\}$: 白–黒
- $\{4,5\}$: 黒–白
- $\{5,6\}$: 白–黒
- $\{6,1\}$: 黒–白
- $\{2,7\}$: 黒–白
- $\{7,8\}$: 白–黒
- $\{8,5\}$: 黒–白
- $\{3,8\}$: 白–黒

どの辺も両端の色が異なるので、$G$ は 2 部グラフである。

$G$ は連結なので、頂点 $1$ を白と決めれば塗り分けはただ 1 通りに定まる。したがって、頂点 $1$ と同じ色の頂点全体の集合は $\{1,3,5,7\}$ である。