「2 色で塗り分けられる」⇔「奇数長の閉路がない」の証明

グラフの話です。

簡単のために、グラフは連結で、多重辺や自己ループがないものとします。

用語の説明

2 色で塗り分けられるとは、次の条件を満たすようにグラフの頂点を 2 色で塗る方法が存在することをいいます。
条件：u と v が辺でつながっている ⇒ u と v は違う色
たとえば
- 四角形のグラフ: 4 頂点で辺が (1, 2), (2, 3), (3, 4), (4, 1) のグラフは 2 色で塗り分けられます。具体的には、頂点 1, 3 を黒に、頂点 2, 4 を白に塗ればいいです。
- 三角形のグラフ: 3 頂点で辺が (1, 2), (2, 3), (3, 1) のグラフは 2 色で塗り分けられません。
奇数長の閉路とは、長さ (= 辺の数 = 通る頂点の種類数) が奇数である閉路をいいます。
- 閉路とは、ある頂点からスタートして同じ辺を使わずに元の頂点へ戻ってくる経路をいいます。
  たとえば
- 四角形のグラフには 1 → 2 → 3 → 4 → 1 という閉路があります。
- 三角形のグラフには 1 → 2 → 3 → 1 という閉路があります。奇数長の閉路です。
- Y のグラフ: 4 頂点で辺が (1, 2), (2, 3), (2, 4) のグラフには閉路がありません。

f:id:poyopoyoyon:20200507140009p:plain — 三角形, 四角形, Y

2 色で塗り分けられる ⇔ 奇数長の閉路がないの使いみちとして、
奇数長の閉路がないかどうかを判定するかわりに
2 色で塗り分けられるかどうかを判定すればいいことになります。

実装例は DFS (深さ優先探索) 超入門！〜グラフ・アルゴリズムの世界への入口〜【後編】 - Qiita を見てください。

証明

2 色で塗り分けられる $\Rightarrow$ 奇数長の閉路がない

こちらはカンタンです。
任意の閉路を取ります。← ここで、閉路がひとつもなかった場合、偶数長の閉路も奇数長の閉路もないため証明終わりです。
この閉路が偶数長の閉路であることを示せばいいです。
頂点番号を適当に付け替えて、閉路が 1 → 2 → ... ... → n → 1 であると考えていいです。
仮定より、2 色で塗り分けられるため、閉路内の各頂点の色は ○ → ● → ... ... → ● → ○ または、これを白黒反転させたものです。
よって 1 から n までに白と黒が同じ個数ずつ現れるため n は偶数です。

2 色で塗り分けられる $\Leftarrow$ 奇数長の閉路がない

d[v]: 頂点 1 から頂点 v までの最短距離 (通る必要のある最小の辺数) とします。

d[v] が偶数 ⇒ v を白に塗る
d[v] が奇数 ⇒ v を黒に塗る

とすれば条件を満たす塗り方になっています。
これを確かめるには

u, v: 白 ⇒ u, v が辺でつながっていない (☆)
u, v: 黒 ⇒ u, v が辺でつながっていない (★)

を示せばいいです。
まず (☆) を示しましょう。
u, v が白だとして、辺でつながっていると仮定します。(背理法です)
すると 1 → ... ... → u → v → ... ... → 1 という閉路ができます。
そして、この閉路の長さは d[u] + 1 + d[v] です。
d[u] + d[v] は偶数なので d[u] + 1 + d[v] は奇数です。
これは奇数長の閉路がないことに矛盾します。
よって (☆) がわかりました。
(★) も同じようにして証明できます。