6.2. グラフの 2-彩色

一方で、グラフに適切な \(2\)-彩色が存在するかどうかを判定する問題はずっと簡単に解ける。次の定理が優れた判定基準となる:

この定理を証明するには、命題 3.3.14 に似た次の命題が必要になる:

この命題で使った直感的な用語を定義しておく:

• 歩道が奇数長 (odd-length) とは、その長さが奇数であることを言う。

• 歩道 \(\mathbf{w}\) が歩道 \(\mathbf{v}\) を含む (contain) とは、\(\mathbf{v}\) の任意の辺が \(\mathbf{w}\) の辺であることを言う (\(\mathbf{w}\) の中に \(\mathbf{v}\) が連続したブロックとして存在する必要はない)。

また、本書で回路 (circuit) は閉歩道を意味する。それ以外に要件は無い。

例 6.2.3

次の単純グラフ (を多重グラフとみなしたもの) を考える:

\(1\) から \(7\) への奇数長の歩道 \(\left( 1,\ast,2,\ast,3,\ast,4,\ast ,5,\ast,2,\ast,6,\ast,7\right) \) は、\(1\) から \(7\) への奇数長の路 \(\left( 1,\ast,2,\ast,6,\ast,7\right) \) を含む (路に含まれる辺は頂点が分かれば自明に分かるので省略している)。

また、奇数長の歩道 \(\left( 3,\ast,2,\ast,1,\ast,6,\ast ,2,\ast,3\right) \) は奇数長の閉路 \(\left( 2,\ast ,1,\ast,6,\ast,2\right) \) を含む。

[命題 6.2.2 の証明] \(\mathbf{w}\) の長さに関する強い数学的帰納法で示す。

帰納ステップ: \(k \in \mathbb{N}\) を任意に取って固定し、長さが \(k\) より小さい奇数長の歩道で命題 6.2.2 が成り立つと (帰納法の仮定として) 仮定する。この仮定を使って、長さ \(k\) の奇数長の歩道 \(\mathbf{w}\) でも同じ命題が成り立つことを示せばよい。

長さ \(k\) の歩道 \(\mathbf{w}\) を \(\mathbf{w}=\left( w_{0},\ast,w_{1},\ast,w_{2},\ldots,\ast,w_{k}\right) \) とする。\(\mathbf{w}\) は奇数長なので、\(k\) は奇数だと分かる。

\(\mathbf{w}\) が \(u\) から \(v\) への奇数長の路または奇数長の閉路を含むと示す必要がある。

\(\mathbf{w}\) 自体が路なら示すべきことはないので、一般性を失うことなく \(\mathbf{w}\) は路でないと仮定する。このとき、\(\mathbf{w}\) の頂点 \(w_{0},w_{1},\ldots,w_{k}\) には同じ頂点の組が少なくとも一つ存在する。言い換えれば、\(0\leq i < j\leq k\) と \(w_{i}=w_{j}\) を満たすように整数 \(i\), \(j\) の組 \(\left( i,j\right) \) が存在する。そのような組の中で、差 \(j-i\) が最小のものを取る。このとき \(w_{i},w_{i+1},\ldots,w_{j-1}\) は相異なる。

\(\mathbf{w}\) の \(w_{i}\) から \(w_{j}\) までの部分を \(\mathbf{c}\) とする¹。つまり \(\mathbf{c}\) を次のように定義する:

\(w_{i} = w_{j}\) より \(\mathbf{c}\) は閉歩道である。さらに、\(\mathbf{c}\) の頂点 \(w_{i},w_{i+1},\ldots,w_{j-1}\) が相異なり、したがって辺も相異なる²ので、\(\mathbf{c}\) は閉路である。もし \(j-i\) が奇数なら、\(w\) は奇数長の閉路 \(\mathbf{c}\) を含む。よって \(j-i\) が奇数の場合を今後考える必要はない。

そこで一般性を失うことなく \(j-i\) が偶数だと仮定する。その上で、歩道 \(\mathbf{c}\) を元の歩道 \(\mathbf{w}\) から除去して得られる次の歩道 \(\mathbf{w}^{\prime}\) に注目する:

\(\mathbf{w}^{\prime}\) は \(\mathbf{w}\) と同様に \(u\) から \(v\) への歩道である。\(k\) が奇数で \(j-i\) は偶数なので \(\mathbf{w}^{\prime}\) の長さは奇数であり、\(i < j\) なので \(\mathbf{w}^{\prime}\) の長さは \(k\) より小さい。よって \(\mathbf{w}^{\prime}\) には帰納法の仮定を適用できる。つまり、\(\mathbf{w}^{\prime}\) は \(u\) から \(v\) への奇数長の路または奇数長の閉路を含む。よって \(\mathbf{w}\) も同様に \(u\) から \(v\) への奇数長の路または奇数長の閉路を含む (\(\mathbf{w}^{\prime}\) に含まれる任意の歩道は \(\mathbf{w}\) にも含まれるため)。これで帰納ステップが完了したので、命題 6.2.2 は証明された。□

続いて \(2\)-彩色の同値性定理を証明する:

[定理 6.2.1 の証明] B1 \(\Longrightarrow\) B2 \(\Longrightarrow\) B3 \(\Longrightarrow\) B1 という論理関係を示す。

B1 \(\Longrightarrow\) B2 の証明: 命題 B1 が成り立つと仮定する。この上で命題 B2 が成り立つと示す必要がある。

命題 B1 が成り立つので、グラフ \(G\) は適切な \(2\)-彩色を持つ。この \(2\)-彩色を \(f\) とする。つまり、\(f\) は \(V\) から \(\left\{ 1,2\right\} \) への写像であり、\(G\) で隣接する任意の二頂点 \(x\), \(y\) に対して \(f\left( x\right) \neq f\left( y\right) \) が成り立つ。

これから \(G\) が奇数長の閉路を持たないことを背理法で示す。\(G\) が奇数長の閉路を持つと仮定する。この閉路を

とする。これは閉路だから \(v_{k}=v_{0}\) であり、\(f\left( v_{k}\right) =f\left( v_{0}\right) \) が成り立つ。また、この閉路は奇数長なので \(k\) は奇数だと分かる。さらに、任意の \(i\in\left\{ 1,2,\ldots,k\right\} \) に対して頂点 \(v_{i}\) と頂点 \(v_{i-1}\) は隣接するので、次が成り立つ:

[\(f\) が適切な \(2\)-彩色であるため。]

一般性を失うことなく \(f\left( v_{0}\right) =1\) と仮定する (そうでなければ色 \(1\) と色 \(2\) の名前を入れ替える)。このとき式 \((1)\) で \(i=1\) とすると \(f\left( v_{1}\right) \neq f\left( v_{0}\right) =1\) が得られ、ここから \(f\left( v_{1}\right) =2\) が分かる (\(f\left( v_{1}\right) \in \left\{1,2\right\} \) より)。今度は式 \((1)\) で \(i=2\) とすると \(f\left( v_{2}\right) \neq f\left( v_{1}\right) =2\) が得られ、ここから \(f\left( v_{2}\right) =1\) が分かる (\(f\left( v_{2}\right) \in \left\{1,2\right\} \) より)。同様の議論を繰り返すと \(f\left( v_{3}\right) =2\), \(f\left( v_{4}\right) =1\), \(f\left( v_{5}\right) =2\), ... が分かる。一般的に表せば次の等式が成り立つ:

[厳密には数学的帰納法による証明が必要となる。] この式で \(i=k\) とすれば、\(k\) は奇数より \(f\left( v_{k}\right) =2\) を得る。しかし、これは \(f\left( v_{k}\right) =f\left( v_{0}\right) =1\neq2\) と矛盾する。この矛盾から仮定が偽だと分かる。よって \(G\) は奇数長の閉路を持たない。言い換えれば、命題 B2 は成り立つ。以上で B1 \(\Longrightarrow\) B2 は証明された。

B2 \(\Longrightarrow\) B3 の証明: 命題 B2 が成り立つと仮定する。この上で命題 B3 が成り立つと示す必要がある。言い換えれば、\(G\) が奇数長の回路を持たないと示せばよい。

背理法で示す。\(G\) が奇数長の回路 \(\mathbf{w}\) を持つと仮定する。\(\mathbf{w}\) の始点かつ終点を \(u\) とする。命題 6.2.2 で \(v=u\) とすると、奇数長の回路 \(\mathbf{w}\) は \(u\) から \(u\) への奇数長の路または奇数長の閉路を含むと分かる。命題 B2 の成立を仮定しているので、\(G\) は奇数長の閉路を含まない。よって \(\mathbf{w}\) は \(u\) から \(u\) への奇数長の路を含むと結論できる。しかしこれは、\(u\) から \(u\) への (唯一の) 路は長さが \(0\) である事実と矛盾する。矛盾が得られたので仮定は偽であり、\(G\) は奇数長の回路を持たない。以上で B2 \(\Longrightarrow\) B3 は証明された。

B3 \(\Longrightarrow\) B1 の証明: 命題 B3 が成り立つと仮定する。この上で命題 B1 が成り立つと示せばよい。

命題 B3 が成り立つと仮定したので、\(G\) は奇数長の回路を持たない。この事実を利用して \(G\) が適切な \(2\)-彩色をもつと示す必要がある。

一般性を失うことなく \(G\) が連結だと仮定する (そうでなければ、\(G\) の成分 \(C_{1},C_{2},\ldots ,C_{k}\) に対する誘導部分グラフ \(G\left[ C_{1}\right] ,\ G\left[ C_{2}\right] ,\ \ldots,\ G\left[ C_{k}\right] \) に B3 \(\Longrightarrow\) B1 を適用し、得られる \(k\) 個の適切な \(2\)-彩色を組み合わせることで \(G\) に対する適切な \(2\)-彩色を得る)。\(G\) の頂点を任意に取って \(r\) として、写像 \(f\colon V\rightarrow\left\{ 1,2\right\} \) を次のように定める:

[ここで \(d\left( v,r\right) \) は \(v\) から \(r\) への距離、つまり \(v\) から \(r\) への路の長さの最小値を表す。]

これから背理法で \(f\) が適切な \(2\)-彩色だと示す³。\(f\) が適切な \(2\)-彩色でないと仮定する。このとき \(G\) で隣接する二頂点 \(u\), \(v\) であって同じ色 \(f\left( u\right) =f\left( v\right) \) を持つものが存在する。\(f\left( u\right) =f\left( v\right) \) より、次の二つの場合が考えられる:

• Case 1: \(f\left( u\right) =f\left( v\right) =1\) が成り立つ。

• Case 2: \(f\left( u\right) =f\left( v\right) =2\) が成り立つ。

Case 2 を考える。\(f\) の定義と \(f\left( u\right) =f\left( v\right) =2\) より、\(d\left( u,r\right) \) と \(d\left( v,r\right) \) が両方とも奇数だと分かる。よって、\(u\) から \(r\) への奇数長の路 \(\mathbf{p}\) と、\(v\) から \(r\) への奇数長の路 \(\mathbf{q}\) が存在する。この \(\mathbf{p}\) と \(\mathbf{q}\) に注目する。\(u\) と \(v\) は隣接するので、\(u\) と \(v\) を接続する辺 \(e\) が存在する。\(\mathbf{p}\), \(e\), \(\mathbf{q}\) をこの順番で利用することで、\(r\) から \(r\) へ移動する回路が得られる (この歩道は最初に \(\mathbf{p}\) に沿って \(u\) に移動し、\(e\) を通じて \(v\) に移動し、\(\mathbf{q}\) を逆走することで \(r\) に移動する)。\(\mathbf{p}\) と \(\mathbf{q}\) は奇数長なので、この回路も奇数長である。よって \(G\) は奇数長の回路を持つ。しかし \(G\) は奇数長の回路を持たないので、矛盾である！

これで Case 2 では矛盾が導けた。Case 1 でも同様の議論で矛盾が導けるので、いずれの場合でも矛盾が避けられない。よって仮定は偽であり、\(f\) は適切な \(2\)-彩色である。よって B1 は成り立つ。以上で B3 \(\Longrightarrow\) B1 は証明された⁴。

より美しい議論も示しておきたいので、B3 \(\Longrightarrow\) B1 の別証明を示す。この証明には、上で示した証明にあった「\(G\) を成分に分解する」という不格好なステップが存在しない。

命題 B3 が成り立つと仮定する。この上で命題 B1 が成り立つと示せばよい。

命題 B3 の成立を仮定したので、\(G\) は奇数長の閉路を持たない。

\(G\) の二頂点 \(u\), \(v\) に対して、\(u\) から \(v\) への奇数長の路が \(G\) に存在するとき \(u\) と \(v\) は奇数接続 (oddly connected) と呼ぶことにする。\(G\) は奇数長の回路を持たないので、この条件は「\(u\) から \(v\) への奇数長の歩道が \(G\) に存在する」に等しい (命題 6.2.2 より)。また、任意の頂点 \(u\) は頂点 \(u\) 自身と奇数接続でない (\(u\) から \(u\) への唯一の路は長さが \(0\) の自明な路 \(\left( u\right) \) であり、これは奇数長でないため)。

\(V\) の部分集合 \(A\) が「\(A\) の任意の二頂点は奇数接続でない」を満たすとき、\(A\) を奇数路欠落 (odd-path-less) と呼ぶことにする。奇数路欠落な \(V\) の部分集合で最大のものを \(A\) とする (\(\varnothing\) は明らかに奇数路欠落なので、そのような \(A\) は存在する)。続いて、\(A\) に含まれる頂点に色 \(1\) を割り当て、\(A\) に含まれない頂点に色 \(2\) を割り当てる写像を \(f\colon V\rightarrow\left\{ 1,2\right\} \) とする。

これから \(f\) が適切な \(2\)-彩色だと示す。

これを証明するには、次の二つの命題を示せばよい:

• 任意の隣接する二頂点が両方とも色 \(1\) を持つことはない。

• 任意の隣接する二頂点が両方とも色 \(2\) を持つことはない。

前者の命題は明らかである⁵。よって後者の命題を示せばよい。

背理法で示す。隣接する二頂点 \(u\), \(v\) が両方とも色 \(2\) を持つと仮定する。この \(u\) と \(v\) に注目する。\(f\) の定義より、色 \(2\) が割り当てられた頂点 \(u\), \(v\) はどちらも \(A\) に属さない。

先述したように、頂点 \(u\) は頂点 \(u\) 自身と奇数接続でない。よって頂点 \(u\) は \(A\) に属する少なくとも一つの頂点 \(a \in A\) と奇数接続である (もしそうでなければ \(A\cup\left\{ u\right\} \) が \(A\) より大きい奇数路欠落な \(V\) の部分集合となるものの、これは \(A\) の最大性と矛盾する)。同様に、頂点 \(v\) は \(A\) に属する少なくとも一つの頂点 \(b \in A\) と奇数接続である。この \(a\) と \(b\) に注目する。\(u\) は \(a\) と奇数接続なので、\(u\) から \(a\) への奇数長の歩道 \(\mathbf{p}\) が存在する。この歩道 \(\mathbf{p}\) を反転すると、\(a\) から \(u\) への奇数長の歩道 \(\mathbf{p}^{\prime}\) が得られる。同様に \(v\) は \(b\) と奇数接続なので、\(v\) から \(b\) への奇数長の歩道 \(\mathbf{q}\) が存在する。最後に、\(u\) と \(v\) は隣接するので、\(u\) と \(v\) を端点に持つ辺 \(e\) が存在する。\(\mathbf{p}^{\prime}\), \(e\), \(\mathbf{q}\) をこの順番で連結すると、\(a\) から \(b\) への歩道が得られる。\(\mathbf{p}^{\prime}\) と \(\mathbf{q}\) は奇数長なので、この歩道も奇数長である。つまり \(G\) は \(a\) から \(b\) への奇数長の歩道を持つ。言い換えれば、\(a\) と \(b\) は奇数接続である。これは \(A\) が奇数路欠落である事実と矛盾する (\(a\) と \(b\) は \(A\) に属するため)。

この矛盾から仮定が偽だと分かる。つまり任意の隣接する頂点が両方とも色 \(2\) を持つことはない。よって \(f\) は適切な \(2\)-彩色であり、命題 B1 が成り立つ。以上で B3 \(\Longrightarrow\) B1 は証明された。

B1 \(\Longrightarrow\) B2 と B2 \(\Longrightarrow\) B3 と B3 \(\Longrightarrow\) B1 を示せたので、三つの命題 B1, B2, B3 は同値だと結論できる。以上で定理 6.2.1 は証明された。□

適切な \(2\)-彩色のさらに単純な性質を次に示す:

[証明 (概略)] \(G\) の任意の成分 \(C\) に対して、任意に頂点を取って \(r_{C} \in C\) とする。\(G\) の適切な \(2\)-彩色を構築するにあたって、頂点 \( r_{C} \) に対する色 \(f\left( r_{C}\right) \) を自由に選ぶ。このとき、\(r_{C}\) 以外の頂点の色は一意に決定する (定理 6.2.1 の B3 \(\Longrightarrow\) B1 の証明を参考)。\(G\) は \(\operatorname*{conn}G\) 個の成分を持つので、適切な \(2\)-彩色には \(2^{\operatorname*{conn}G}\) 個の選択肢が存在する。以上で示したい命題は証明された。□