グラフ理論の問題

2 部グラフかどうかを判定するには、1 つの頂点から始めて「隣の頂点には反対の色を塗る」ことをくり返し、矛盾（同じ色の頂点どうしを結ぶ辺）が出ないかを調べる。

手順 1（頂点 1 から塗る） 頂点 $1$ を赤にする。$1$ と隣接する頂点は $3,5$ なので、$3,5$ を青にする。

手順 2（青の頂点の隣を塗る） 頂点 $3$ に隣接する頂点は $1,2,4$、頂点 $5$ に隣接する頂点は $1,2,6$ である。まだ塗っていない $2,4,6$ を赤にする。

手順 3（赤の頂点の隣を塗る） 頂点 $2$ に隣接する頂点は $3,5,7$、頂点 $4$ に隣接する頂点は $3,7$、頂点 $6$ に隣接する頂点は $5,7$ である。まだ塗っていない $7$ を青にする。

これで全頂点が塗れた：
$$\text{赤}=\{1,2,4,6\},\text{青}=\{3,5,7\}.$$

手順 4（すべての辺を確認）
$\{1,3\}$: 赤–青, $\{1,5\}$: 赤–青, $\{2,3\}$: 赤–青, $\{2,5\}$: 赤–青, $\{2,7\}$: 赤–青, $\{3,4\}$: 青–赤, $\{4,7\}$: 赤–青, $\{5,6\}$: 青–赤, $\{6,7\}$: 赤–青。
どの辺も両端の色が異なるので矛盾はなく、$G$ は 2 部グラフである。したがって「2 部グラフ $⟺$ 奇数長の閉路をもたない」より、$G$ には奇数長の閉路がない（実際、たとえば閉路 $1\text{–}3\text{–}2\text{–}5\text{–}1$ の長さは $4$、閉路 $2\text{–}3\text{–}4\text{–}7\text{–}2$ の長さも $4$ で偶数である）。

塗り方が一意であること $G$ は連結である（$1\text{–}3\text{–}2\text{–}5\text{–}6\text{–}7\text{–}4$ とすべての頂点をたどれる）。上の手順では、頂点 $1$ の色を決めると各頂点の色は辺をたどって強制的に決まったので、頂点 $1$ を赤とする塗り方はこれ 1 通りである。

よって赤で塗られる頂点の集合は $\{1,2,4,6\}$ である。

グラフは連結なので、頂点 $1$ の色を決めると全頂点の色が一意に決まる。
頂点 $1$ を赤とする。
- $1$ に隣接する $3,5$ は青。
- $3$ に隣接する $2,4$ は赤（$1$ は赤で整合）。
- $5$ に隣接する $2,6$ は赤（$2$ は先の結果と一致）。
- $2$ に隣接する $7$ は青（$3,5$ は青で整合）。

赤は $\{1,2,4,6\}$、青は $\{3,5,7\}$ となる。

検算として全 $9$ 本の辺の両端の色を調べる。
$\{1,3\}$: 赤-青、$\{1,5\}$: 赤-青、$\{2,3\}$: 赤-青、$\{2,5\}$: 赤-青、$\{2,7\}$: 赤-青、$\{3,4\}$: 青-赤、$\{4,7\}$: 赤-青、$\{5,6\}$: 青-赤、$\{6,7\}$: 赤-青。
どの辺も両端の色が異なるので、条件を満たす。

よって赤で塗られる頂点全体の集合は $\{1,2,4,6\}$。