13.6 平面グラフの彩色

これまでに平面グラフに関する基礎的な事実をいくつか示したものの、有名な四色定理を証明するには十分でない。ただ、非常に近いところまでは到達できる。実は、あと少しだけ準備すれば全ての平面グラフが \(5\) 色で彩色できることを示せる。

まず、平面グラフに関する簡単な事実をいくつか示す。以降の議論で利用される。

補題 13.6.1

平面グラフの任意の部分グラフは平面グラフである。

補題 13.6.2

平面グラフで隣接する二頂点を融合して得られるグラフは平面グラフである。

隣接する二頂点 \(n_{1}\), \(n_{2}\) を融合 (merge) するとは、二つの頂点を除去し、「融合」された頂点 \(m\) を一つ新たに追加し、\(n_{1}\) または \(n_{2}\) に隣接する全ての頂点を \(m\) に隣接させる操作を意味する。融合の例を図 \(\text{13.12}\) に示す。

隣接する二頂点 n_{1}, n_{2} を融合すると、二頂点が新しい頂点 m で置き換わる。
図 13.12隣接する二頂点 \(n_{1}\), \(n_{2}\) を融合すると、二頂点が新しい頂点 \(m\) で置き換わる。

多くの著者は定義 13.2.1 が定める連続な平面描画に対する補題 13.6.1 と補題 13.6.2 を当然のものとして扱い、証明を与えない。しかし再帰的定義 (定義 13.2.2) があれば、構造的帰納法を使って実際に証明できる (問題 13.9)。

必要になる補題がもう一つだけある:

補題 13.6.3

全ての平面グラフには、次数が \(5\) 以下の頂点が存在する。

証明 背理法で示す。平面グラフの全ての頂点の次数が \(6\) 以上だと仮定する。このとき頂点の次数の和は \(6v\) 以上である。握手補題 (補題 12.2.1) より頂点の次数の和は \(2e\) に等しいので、\(2e \geq 6v\) すなわち \(e \geq 3v\) を得る。しかし定理 13.4.3 からは \(e \leq 3v - 6 < 3v\) が分かるので、これは矛盾である。 ■

定理 13.6.4

全ての平面グラフは \(5\)-彩色可能である。

証明 頂点の個数 \(v\) に関する強い数学的帰納法で示す。次の述語 \(P(v)\) を帰納法の仮定とする:

\[ P(v) \ \ \overset{\text{def}}{\longleftrightarrow}\ \ \text{\(v\) 個の頂点を持つ全ての平面グラフは \(5\)-彩色可能である。} \]

ベースケース: \(v \leq 5\) のとき、\(P(v)\) は明らかに成り立つ。

帰納ステップ: \(G\) を \(v + 1\) 個の頂点を持つ平面グラフとする。これから \(G\) の \(5\)-彩色を構築する。

まず、次数が \(5\) 以下の \(G\) の頂点を \(g\) とする。補題 13.6.3 が \(g\) の存在を保証する。以降の議論は二つの場合に分かれる:

■

広告