next up previous
Next: この文書について... (PDF ��������: planar.pdf)

平成 13 年 6 月 21 日
$K_{3,3}$ と $K_5$ が平面グラフでないことの証明
新潟工科大学 情報電子工学科 竹野茂治

教科書 p.96 例 3.6 に $K_5$ が平面グラフでないことの証明が載っているが、 一箇所説明不足の点がある ( $\vert E\vert\geq 7\times 3/2$)。その話を含めて $K_{3,3}$ と $K_5$ が平面グラフでないことの証明を行う。

以下、$R$, $\vert E\vert$, $\vert V\vert$ 等の記号の意味については教科書参照のこと。


補題 1

平面グラフが単純グラフであるとき、$R\geq 2$ ならば

\begin{displaymath} 3R\leq 2\vert E\vert \end{displaymath}


証明

交差する辺のない単純グラフでは、外部領域も含め全ての領域が 3 本以上の辺に囲まれている。

そして、各辺は 2 つの領域を分けているから、各領域を囲む辺を 全て数え上げると各辺を 2 度数えることになるので

\begin{displaymath} \mbox{各領域を囲む辺の数の合計} = \mbox{(辺の数)}\times 2 \geq 3\times\mbox{(領域の数)} \end{displaymath}

となる。



補題 2

三角形が含まれない単純平面グラフでは、$R\geq 2$ に対して

\begin{displaymath} 4R\leq 2\vert E\vert \end{displaymath}


証明

補題 1 の証明の論法により明らか (全ての領域が 4 本以上の 辺に囲まれる)。


例えば、平面 2 部グラフには三角形はない (奇数角形はない) ので、この 不等式が成り立つ。


系 3

完全 2 部グラフ $K_{3,3}$ は平面グラフではない。


証明

$K_{3,3}$ は $\vert E\vert=9$, $\vert V\vert=6$, $k=1$ なので、もし平面グラフの形に 書けたとすると、オイラーの公式により

\begin{displaymath} R=k+1-\vert V\vert+\vert E\vert=1+1-6+9=5 \end{displaymath}

でなければならないが、補題 2 により

\begin{displaymath} 4R\leq 2\vert E\vert \end{displaymath}

でならなければならず、それは $4R=20$, $2\vert E\vert=18$ に矛盾する。



系 4

完全グラフ $K_5$ は平面グラフではない。


証明

上の証明で $\vert E\vert=10$, $\vert V\vert=5$ とし、補題 1 を使えば 全く同様に証明できる。


$K_{1,n}$, $K_{2,n}$, $K_4$ は明らかに平面グラフなので、$K_{m,n}$, $K_n$ のうち平面グラフは $K_{1,n}$, $K_{2,n}$, $K_{j}$ ($j=1,2,3,4$) となる。

そして、逆に、一般のグラフが平面グラフである必要十分条件は、 $K_{3,3}$ や $K_5$ を本質的に部分グラフとして含まないこと、 であることがクラトウスキー (C.Kuratowski 1896-1980 ポーランド) によって 示されている。

なお、上のような不等式を用いない図形的な考察による証明もある。 そして、その証明を見ると、球面上でも $K_{3,3}$ や $K_5$ は 交差せずに書くことは出来ないが、トーラス上では交差せずに書ける ことが分かる。


next up previous
Next: この文書について...
Shigeharu TAKENO
2001年 8月 9日