13.5 再訪: \(K_{5}\) と \(K_{3,3}\)

本章の冒頭で考えた quadrapus の握手に関するパズルに答える準備がこれで整った: \(5\) 匹の quadrapus が海底で互いに握手するとき、手は必ず交差するだろうか？ 先述したように、このパズルは完全グラフ \(K_{5}\) が平面かどうかを尋ねている。そして定理 13.4.3 からは次の系が直ちに得られる:

証明 \(K_{5}\) は \(5\) 個の頂点と \(10\) 個の辺を持つ連結なグラフである。\(e = 10 > 3 \cdot 5 - 6 = 3v - 6\) が成り立つので、\(K_{5}\) は不等式 \(\text{(13.3)}\) を満たさない。よって定理 13.4.3 より \(K_{5}\) は平面グラフでない。 ■

\(K_{3,3}\) が平面グラフでないことは Euler の公式を使うと示せる。ここに示す証明は定理 13.4.3 の証明と似ているものの、\(K_{3,3}\) が二部グラフである事実を利用する点が異なる。

証明 補題 13.4.2 より、連結なグラフの平面埋め込みに属する離散面の長さは \(3\) 以上である。一方で補題 12.6.2 と定理 12.8.3 の \(\text{3.}\) からは、二部グラフが奇数長の閉歩道を持たないと分かる。平面埋め込みの離散面は閉歩道なので、二部グラフの離散面の長さが \(3\) になることはない。よって \(3\) 個以上の頂点を持つ連結な二部グラフの平面埋め込みでは、任意の離散面の長さが \(4\) 以上である。 ■

証明 補題 13.5.2 より、\(3\) 個以上の頂点を持つ任意の平面二部グラフの平面埋め込みにおいて任意の離散面の長さは \(4\) 以上である。よって定理 13.4.3 の証明と同様の議論から、離散面の長さの和がちょうど \(2e\) かつ \(4f\) 以上だと分かる。つまり、\(3\) 個以上の頂点を持つ任意の平面二部グラフの平面埋め込みで次の不等式が成り立つ:

Euler の公式より \(f = 2 - v + e\) が成り立つので、不等式 \(\text{(13.5)}\) の \(f\) に代入すれば次を得る:

これを整理すれば不等式 \(\text{(13.5)}\) となる。 ■

証明 \(K_{3,3}\) は \(6\) 個の頂点と \(9\) 個の辺を持つ連結二部グラフである。\(e = 9 > 2 \cdot 6 - 4 = 2v - 4\) なので、\(K_{3,3}\) は不等式 \(\text{(13.5)}\) を満たさない。よって定理 13.5.3 より \(K_{3,3}\) は平面グラフでない。 ■