6 グラフの交差数
演習 39 一般の n, m に対し，図 38を参考に最適と思われる埋め込みを与えよ．またそ の交点数が，予想 63の式の右辺と一致することを示せ．
ここでは，予想 63の n= 3 の場合を定理 58を用いて示す．
定理 65 予想 63は K3,m の場合は正しい．
証明． 定理 64より上界は正しいので，下界のみを示せばよい．すなわち，K3,m の任 意の描画において，交点が
⌊3 2
⌋⌊2 2
⌋⌊m 2
⌋⌊m−1 2
⌋
=
⌊m 2
⌋⌊m−1 2
⌋
個以上存在することを示す．
y1
y2
y3
x1
x2
x3
y1 y3
y2 y4
y4
図 39: K3,4 の描画とそれからできるグラフH．(X ={x1, x2, x3} としている．)
K3,m の頂点を X∪Y とおく．ただし，3頂点側の頂点集合を X，m 頂点側の頂点集 合を Y とする．また y∈Y に対し，y に接続する K3,m の辺の集合を E(y) とおく．す なわち，|E(y)|= 3 である．ここで，K3,m の一つの描画φに対して，Y を頂点集合とす るグラフ H を次のように構成する．
Y の 2頂点 y1, y2 に対し，E(y1)のある辺と E(y2) のある辺がφ において交 わるとき，かつそのときに限り，H において y1 と y2 を辺で結ぶ．
つまり，
E(H) = {y1y2 : E(y1) と E(y2)が φにおいて交差する}
である．(図 39 参照) このとき，φ における交点の数は少なくとも |E(H)| 以上である ため，
|E(H)| ≥⌊m 2
⌋⌊m−1 2
⌋
を示せばよい．そのために，H の補グラフH を考える．これは，H と同じ頂点集合を持 ち，H において隣接しない2頂点を辺で結んだグラフである．(すなわち，E(H) ={y1y2 : y1y2 ̸∈E(H)} である.) ここで，K3,3 が平面的でないことより，次の主張が成り立つ．
主張 65.1 H は三角形を持たない．
仮に，H が三角形y1y2y3 を持ったとすると，H とH の定義より E(y1), E(y2), E(y3)の どの辺も交差しないが，これは X と y1, y2, y3 によるK3,3 が辺の交差なく平面に描けて いることになり，K3,3 が平面的ではないことに矛盾する．
したがって，定理 58 よりH の辺数の上界が計算できる．すなわち，
|E(H)| ≤ ⌊m 2
⌋⌈m 2
⌉
である．これより |E(H)|の下界が求まる．
|E(H)| = (m
2 )
− |E(H)| ≥ m(m−1) 2 −⌊m
2
⌋⌈m 2
⌉
=
⌊m 2
⌋⌊m−1 2
⌋
. □
また，次の漸化式が知られており，これより，予想 63は n (および m) が奇数のとき が本質的であるとわかる．
定理 66 任意の正の整数 n, m に対し次が成り立つ．
cr(Kn,m)≥ n
n−2 cr(Kn−1,m).
証明． 完全 2部グラフ Kn,m の平面への描画で交点数が最小のものを考える．このと き，次の集合 S を 2通りに数える：
S = {
(p, H) : p は Kn,m の描画における交点，
H は Kn−1,m と同型な部分グラフでpがやはり交点となるもの} . まず，Kn,m において，n 頂点側の部集合のうちのn−1頂点を固定し，Kn−1,m と同型 な部分グラフ H を考える．交差数の定義より，H は少なくとも cr(Kn−1,m) 個の交点を 持つ．また，そのような H の選び方は n 通りあり，したがって，
|S| ≥n·cr(Kn−1,m)
である．一方で，Kn,m の各交点 p を考える．交点 p には Kn,m の n 点側の部集合のう ちの 2頂点が関わり，その2頂点を含むような H で pはやはり交点となっている．その ような H は n−2 個存在し，交点p は cr(Kn,m)個存在するため，
|S|= (n−2)·cr(Kn,m) を得る．これより，定理 66の証明が完了する． □
演習 40 定理 66を利用し，予想 63は n が奇数のときのみを解けばよいことを示せ．特 に，予想は K4,m の場合には正しいが，これを示せ．
なお，完全グラフ Kn の交差数 cr(Kn)についても完全2部グラフのときと同様の予想 が提案されている．これも，上界は示されている．すなわち，Kn の“良さそうな”描画 が示されており，残る問題はそれが最善であると示すことである．
予想 67 (Hill, 1960) 正の整数 n に対し，次が成り立つ．
cr(Kn) = 1 4
⌊n 2
⌋⌊n−1 2
⌋⌊n−2 2
⌋⌊n−3 2
⌋ ,
演習 ∗ 予想67 の上界は正しいことを，Kn の“良さそうな”描画を与えることで示せ．
この予想は n≤12 では正しいことが示されているが，一般には難しい．また，次の演 習より，予想 67は n が奇数のときが本質的であるとわかる．
演習 41 任意の正の整数 n に対し，次が成り立つことを示せ．
cr(Kn)≥ n
n−4 cr(Kn−1).
なお，交差数にはさまざまなバリエーションが知られており，それぞれで上のような問 題が考えられている．例えば，“各辺を直線分で描く” という制限を付けたものは線形交 差数 (rectilinear crossing number) と呼ばれている．これに関しては，完全グラフ Kn に おいて n≤27 まで決定されている．
演習 42 cr(K6) = 3 を示せ．