第10章第1節

省略。

グラフ$G$が平面的ならば$G$の平面描画を固定して細分の配置を考えれば$G$の細分は平面的である。任意の細分が平面的なグラフ$G$について、各辺をちょうど一度細分したグラフを考える。このグラフの平面描画から細分された頂点を辺で置き換えれば$G$の平面描画が得られる。

省略。

a)平面的グラフはマイナーについて閉じていることから明らか。
b)$K_5$が反例。

$n=4$のとき$G=K_4$より正しい。ある$n>4$について$4\leq v(G)< n$を満たす任意の$G$が$K_4$の細分を含むと仮定する。$v(G)=n$のとき、次数が最小の頂点を$v$とする。$d(v)=0$または$d(v)\geq4$のとき、$\delta(G-v)\geq3$なので帰納法の仮定から$G-v$は$K_4$の細分を含む。よって$G$も$K_4$の細分を含む。$d(v)=2,3$のとき、$G^\p$を$G-v$に対して(必要であれば)$N(v)$から選んだ二頂点の間に辺を付け加えたグラフとする。$G^\p$は帰納法の仮定から$K_4$の細分を含み、$G^\p$の構成から$G$も$K_4$の細分を含む。$d(v)=1$のとき、帰納法の仮定から$G-v$は$K_4$の細分を含み、$G$が$K_4$の細分を含むことが従う。

省略。

グラフ$G$が$m$-bookに埋め込めることを示す。任意の頂点を背表紙に埋め込み、各辺を異なるページに埋め込むとこれは$G$の$m$-bookへの埋め込みである。有限の$m$に対して$m$-bookは$\mR^3$に埋め込めるので$G$は$\mR^3$に埋め込める。

a)明らか。
b)実際に$cr(G)=1$となる埋め込みを構成すれば良い。省略。
c)$cr(P_{10})=k$とすると、$k\leq2$は実際に描画することで分かる。$P_{10}$の平面描画において交差している部分の辺をひとつづつ取り除いた平面グラフ$G$を考える。$v(G)=10$、$e(G)=15-k$であり、$P_{10}$はgirth $5$なので$2(15-k)\geq2\cdot5+5(15-k)-5\cdot10$が成り立つ。これを解くと$k\geq\frac{5}{3}$なので、$k=2$である。
d)$cr(K_6)=k$とすると、$k\leq3$は実際に描画することで分かる。$K_6$の平面描画において交差している部分の辺をひとつづつ取り除いた平面グラフ$G$を考える。$v(G)=6$、$e(G)=15-k$なので、$2(15-k)\geq2\cdot3+3(15-k)-3\cdot6$が成り立つ。$k\geq3$なので、$k=3$である。

$\frac{cr(G)}{_nC_4}\geq\frac{1}{5}$を帰納法で示し、単調非減少であることを示す。
$n=5$のときは問題8(b)より正しい。ある$n-1\geq6$に対して不等式が成り立つと仮定する。
$K_n$から任意に頂点を取り除くと$K_{n-1}$となる。$K_n$を交差数が$cr(G)$となるように平面に描画する。ある交差$c$に注目するとこれは接続しない二つの辺$uv$と$xy$の交差である。$K_n$から任意に頂点を取り除いたグラフは$u,v,x,y$を取り除いたときを除いて交差$c$は解消されていない。よって、各頂点を取り除いた部分グラフをすべて考えると、交差数の和は$(n-4)cr(K_n)$以下である。以上の議論と帰納法の仮定より、$(n-4)cr(K_n)\geq ncr(K_{n-1})\geq\frac{n}{5}\ _{n-1}C_4$が成り立つので、任意の$n\geq5$について$\frac{cr(G)}{_nC_4}\geq\frac{1}{5}$が成り立つ。

$G$を交差数が$cr(G)$と一致するように平面に埋め込む。$G$は辺推移的なので自己同型を用いて埋め込みを固定したまま頂点の添え字を入れ替えることで辺$e$が異なる辺と交差するようにできる。よって、$G$は交差極小。