二部グラフ
定義
グラフ $G = (V,E)$ が二部グラフ (bipartite graph) であるとは、$V$ の分割 $V=A\cup B$, $A\cap B=\emptyset$ が存在して、$A$ の点どうし、もしくは $B$ の点どうしをつなぐ辺が存在しないようにできることをいう。
より一般に、正整数 $r$ について、$G$ が $r$-部グラフ ($r$-partite graph) であるとは、同様に $V$ の分割 $V=\bigcup_{i=1}^r A_i$ （$i\neq j$ のとき $A_i\cap A_j=\emptyset$）が存在して $1\leq i \leq r$ について頂点 $v_1, v_2 \in A_i$ を任意に選んだとき $v_1$ と $v_2$ のあいだに辺がないようにできることをいう。
このとき $A_i$ を頂点のクラス (class)という。
完全 $r$-部グラフ
完全 $r$-部グラフ (complete $r$-partite graph) とは、異なるクラスの頂点をすべて辺で結んだグラフをいう。つまり、
頂点のクラスが $A_i ~ (i=1, \ldots, r)$ である完全 $r$-部グラフとは、
$$V=\bigcup_{i=1}^r A_i, ~ E=\{(v, w): v\in A_i, w\in A_j \exists i, j[1\leq i< j\leq r]\}$$
によって定まるグラフである。
$\abs{A_i}=n_i$ となる完全 $r$-部グラフを $K(n_1, \ldots, n_r)$ によりあらわす。完全二部グラフ $K(p, q)$ を $K_{p, q}$ と、完全 $r$-部グラフ $K(t, \ldots, t)$ を $K_r(t)$ とかくこともある。
完全 $r$-部グラフ $K(n_1, \ldots, n_r)$ は、グラフの和を用いて
$$K(n_1, \ldots, n_r)=E_{n_1}+E_{n_2}+\cdots +E_{n_r}$$
とあらわされる。とくに完全二部グラフ $K_{p, q}$ は
$$K_{p, q}=E_p+E_q=\overline{K_p+K_q}$$
とあらわされる。
基本的事実
二部グラフにおいて、同じクラスの頂点どうしを結ぶ道の長さは偶数でなければならない。実際、$G=(V, E)$ が二部グラフであるし、そのクラスを $A$, $B$ とおく。$A$ の$2$頂点 $u$, $v$ を結ぶ道を $u_0=u, \ldots, u_n=v$ とおくと $k$ が奇数のとき $u_k\in B$, $k$ が偶数のとき $u_k\in A$ となるから $n$ は偶数でなければならない。同様に、$B$ の$2$頂点 $u$, $v$ を結ぶ道の長さも偶数でなければならない。
二部グラフはつぎのように特徴づけられる。
グラフ $G=(V, E)$ が二部グラフであるための必要十分条件は、$G$ が長さが奇数のサイクルをもたないことである。
$G=(V, E)$ が二部グラフであるとき、同一のクラスに属する頂点 $u$, $v$ を結ぶ道の長さは偶数でなければならない。
とくに $u=v$ とおくことで、$u$ を含むサイクルの長さは偶数でなければならない。つまり、$G$ には長さが奇数のサイクルは存在しない。
逆に、$G=(V, E)$ が長さが奇数のサイクルをもたないグラフとする。
まず、$G$ が連結グラフであるとする。
$G$ の頂点 $v$ をひとつとり、$U$ を $v$ からの距離が奇数である頂点全体の集合、$W$ を $v$ からの距離が偶数である頂点全体の集合とする。$G$ は連結としているので、$V=U\cup W$ となる。
$f=0, 1$ のいずれかとし、$d(x)\equiv d(y)\equiv f\Mod{2}$ となる $2$点 $x$, $y$ を結ぶ辺 $xy$ が存在するとする。$x$ と $v$ を結ぶ最短のパスをとり、$x_0=x, \ldots, x_{2m+f}=v$ とおく。同様に $y$ と $v$ を結ぶ最短のパスをとり、$y_0=y, \ldots, y_{2n+f}=v$ とおく。
$x_s=y_t$ となる $t$ が存在する最小の $s$ をとり、$x_s=y_t$ となる $t$ をとる（$y_0=y, \ldots, y_{2n+f}=v$ はパスだから、このような $t$ は一意に定まる）と、
$$x=x_0, \ldots, x_s=y_t, y_{t-1}, \ldots, y_0=y$$
は $x$ と $y$ を結ぶ長さ $s+t$ のパスとなるので、これに $xy$ を加えたものは長さ $s+t+1$ のサイクルとなる。
$2m+f-s=2n+f-t$ となることを示す。$2m+f-s>2n+f-t$ とする。
$$x=x_0, \ldots, x_s=y_t, \ldots, y_{2n+f}=v$$
は $x$ と $v$ を結ぶ歩道となるから、$x$ と $v$ を結ぶ、長さ $s+2n+f-t$ 以下のパスが存在する（$0\leq i\leq s-1$ のとき、$x_i=y_j$ となる $y_j$ は存在しないから、上記の頂点は相異なる頂点となるので、上記の歩道自体が実はパスとなる）。
しかし、このパスの長さは $s+2n+f-t<2m+f$ となって、$x_0=x, \ldots, x_{2m+f}=v$ が $x$ と $v$ を結ぶ最短のパスであることに反する。
つぎに $2m+f-s<2n+f-t$ とする。
$$y=y_0, \ldots, y_t=x_s, \ldots, x_{2m+f}=v$$
をとるは $y$ と $v$ を結ぶ歩道となるから、$y$ と $v$ を結ぶ、長さが $t+2m+f-s<2n+f$ のパスが存在することになり、
$y_0=y, \ldots, y_{2n+f}=v$ が $y$ と $v$ を結ぶ最短のパスであることに反する。
よって、$2m+f-s=2n+f-t$ つまり $s-t=2(m-n)$ でなければならないから、$s\equiv t\Mod{2}$ となる。よって $s+t+1$ は奇数となるので、
$$x=x_0, \ldots, x_s=y_t, y_{t-1}, \ldots, y_0=y, x$$
は長さが奇数のサイクルとなって、$G$ が長さが奇数のサイクルをもたないという仮定に反する。
したがって、$d(x)\equiv d(y)\Mod{2}$ となる$2$点 $x$, $y$ を結ぶ辺 $xy$ は存在しない。つまり $U$ の頂点同士を結ぶ辺も $W$ の頂点同士を結ぶ辺も存在しないから、$G$ は $U$, $W$ からなる二部グラフである。
$G$ が連結でない場合も、各連結成分 $G_i$ は上記の議論からクラス $U_i$, $W_i$ からなる二部グラフとなるから、
$G$ は $\bigcup_i U_i$, $\bigcup_i W_i$ からなる二部グラフとなる。
