グラフ理論の問題

$K_{4,4}$ の頂点数は $n=8$、辺の数は $e=4\times 4=16$ である。

準備：平面二部グラフの辺数の上界. 頂点数 $n\ge 3$ の単純な平面グラフ $H$ が二部グラフ（したがって長さ $3$ の閉路をもたない）とする。まず $H$ が連結で辺を $2$ 本以上もつとき、平面に交差なく描いたときの頂点数・辺数・面の数を $n,e^{\prime },f$ とすると、オイラーの公式より $n-e^{\prime }+f=2$。三角形がないので各面の境界の長さ（辺を数えた回数）は $4$ 以上であり、各辺はちょうど $2$ 回数えられるので $4f\le 2e^{\prime }$。よって $f\le e^{\prime }/2$ で、
$$2=n-e^{\prime }+f\le n-\frac{e^{\prime }}{2}⟹e^{\prime }\le 2n-4.$$
連結でない場合も、辺を追加して連結にしても平面性と二部性を保てる（各連結成分を外側の面で 1 本の辺でつなぐ。二部性はつなぐ頂点の側を選べば保てる）ので、同じ不等式 $e^{\prime }\le 2n-4$ が成り立つ。

下界. $K_{4,4}$ の交差数 $k$ の描き方があるとする。交差点が残っている限り、その交差点を通る辺を 1 本取り除くと、交差点は少なくとも 1 つ減る。したがって高々 $k$ 本の辺を取り除けば交差のない描き方、すなわち平面グラフが得られる。これは $8$ 頂点の二部グラフで、辺は $16-k$ 本以上ある。上の不等式より
$$16-k\le 2\cdot 8-4=12⟹k\ge 4.$$

上界（交差数 $4$ の描き方）. 座標平面で、$A$ の頂点を $(-2,0),(-1,0),(1,0),(2,0)$、$B$ の頂点を $(0,-2),(0,-1),(0,1),(0,2)$ に置き、辺をすべて線分で描く。$A$ の頂点 $(a,0)$ と $B$ の頂点 $(0,b)$ を結ぶ線分は、$a,b$ の符号で決まる 1 つの象限（と軸上の端点）の中にあるので、異なる象限にある 2 本の線分は交わらない。各象限には $2\times 2=4$ 本の線分があり、たとえば第 1 象限では $(1,0)$-$(0,2)$ と $(2,0)$-$(0,1)$ の 1 組だけが交わる（端点を共有する組は端点以外で交わらず、$(1,0)$-$(0,1)$ と $(2,0)$-$(0,2)$ は平行で交わらない）。ほかの象限も対称なので、交差点は合計 $4\times 1=4$ 個であり、3 本の辺が 1 点で交わることもない。

以上より、交差数の最小値は $4$ である。

$K_{m,n}$ の交差数については、Zarankiewicz の予想が $\min \text{cr}(K_{m,n})=\lfloor \frac{m}{2}\rfloor \lfloor \frac{m-1}{2}\rfloor \lfloor \frac{n}{2}\rfloor \lfloor \frac{n-1}{2}\rfloor$ であり、$\min (m,n)\le 6$ のときは Kleitman により成り立つことが証明されている。$m=n=4$ では
$$2\cdot 1\cdot 2\cdot 1=4.$$

上界: Zarankiewicz の描き方（$A$ の頂点を $x$ 軸上に原点の両側へ 2 個ずつ、$B$ の頂点を $y$ 軸上に原点の両側へ 2 個ずつ置き、辺を線分で描く）では交差が 4 個になる。
下界の確認: $K_{4,4}$ は辺数 16、頂点数 8 で、二部グラフ（三角形なし）の平面グラフは辺数 $\le 2\cdot 8-4=12$ なので、辺を 1 本ずつ取り除くたびに交差が少なくとも 1 本分減ることを使うと、少なくとも $16-12=4$ 個の交差が必要。実際、交差数 $c$ の描き方では、交差ごとに 1 辺を除くと平面描画が得られ、$16-c\le 12$ から $c\ge 4$。

よって最小値は 4。