グラフ理論の問題

頂点を 2 色（赤・青）で塗り分けます。ルールは「辺で結ばれた 2 頂点は必ず異なる色にする」です。

手順 1（出発点を決める） 頂点 $1$ を赤にします。

手順 2（隣の頂点の色を決める） 頂点 $1$ と隣り合う頂点は $2,5$ なので、$2,5$ は青です。

手順 3（さらに隣へ広げる）
- 頂点 $2$（青）と隣り合う未着色の頂点は $4$ なので、$4$ は赤。
- 頂点 $5$（青）と隣り合う未着色の頂点は $6,7$ なので、$6,7$ は赤。
- 頂点 $4$（赤）と隣り合う未着色の頂点は $3,8$ なので、$3,8$ は青。

これで全頂点の色が決まりました：赤 $=\{1,4,6,7\}$、青 $=\{2,3,5,8\}$。

手順 4（すべての辺を確認する）
$\{1,2\}$：赤-青、$\{1,5\}$：赤-青、$\{2,4\}$：青-赤、$\{3,4\}$：青-赤、$\{3,6\}$：青-赤、$\{4,8\}$：赤-青、$\{5,6\}$：青-赤、$\{6,8\}$：赤-青、$\{3,7\}$：青-赤、$\{5,7\}$：青-赤。
どの辺も両端の色が異なるので、矛盾なく 2 色に塗り分けられました。よって $G$ は 2 部グラフです。

もし $G$ に奇数長の閉路があれば、その閉路を一周する間に色が赤・青と交互に変わるため、奇数回の交代で出発点に戻り、出発点と同じ色の頂点が隣り合う矛盾が起きます。塗り分けに成功したことは「$G$ は奇閉路をもたない」ことと対応しています（2 部グラフ $⟺$ 奇数長の閉路をもたない）。

手順 5（分け方が一通りであること） $G$ は連結です（$1$ から辺をたどってすべての頂点に到達できました）。連結なグラフでは、1 つの頂点の色を決めると、隣の頂点の色が次々に強制的に決まるので、2 つの集合への分け方はただ一通りです。

したがって、頂点 $1$ を含む方の集合は
$$\{1,4,6,7\}$$
です。

グラフが連結なので、頂点 $1$ の属する側を決めれば分け方は一意に決まる。
$1\in X$ とおく。
- $1$ の隣接頂点 $2,5$ は $Y$ に属する。
- $2$ の隣接頂点 $4$ は $X$ に属する。$5$ の隣接頂点 $6,7$ も $X$ に属する。
- $4$ の隣接頂点 $3,8$ は $Y$ に属する。

よって $X=\{1,4,6,7\}$、$Y=\{2,3,5,8\}$ となる。

検算として、10 本の辺がすべて $X$ と $Y$ にまたがることを確かめる。
- $\{1,2\}$: $X$–$Y$
- $\{1,5\}$: $X$–$Y$
- $\{2,4\}$: $Y$–$X$
- $\{3,4\}$: $Y$–$X$
- $\{3,6\}$: $Y$–$X$
- $\{4,8\}$: $X$–$Y$
- $\{5,6\}$: $Y$–$X$
- $\{6,8\}$: $X$–$Y$
- $\{3,7\}$: $Y$–$X$
- $\{5,7\}$: $Y$–$X$

どの辺も条件を満たす。したがって頂点 $1$ を含む集合は $\{1,4,6,7\}$ である。