グラフの定義

平面グラフ

グラフ彩色

Adrian Bondy, U.S.R. Murty著Graph Theoryの演習問題の解答を掲載する。

Graph Theory演習問題解答

#平面グラフの定義

$F(K_5,K_{3,3})$に含まれるグラフを平面グラフと呼ぶ。

# グラフの定義

まずはグラフを定義する。

有限集合$V$と$V$の部分集合の族$E$の対$G=(V,E)$を**ハイパーグラフ** (*hypergraph*)と呼ぶ。

$E$が異なる$k$個の元からなる$V$の部分集合の族のとき、$G=(V, E)$ を$k$-ハイパーグラフという。特に$E$が異なる$2$元からなる$V$の部分集合の族のとき、$G=(V,E)$を単純グラフと呼ぶ。

$V$ の異なる $k$ 個の要素全体のなす集合を $[V]^k$ によりあらわす。$k$-ハイパーグラフは、$E\subset [V]^k$ となる、対 $(V, E)$ のことであり、グラフは、$E\subset [V]^2$ となる、対 $(V, E)$ のことである。

以下では単純グラフのことを**グラフ** (*graph*)と呼ぶ。

グラフ$G=(V,E)$の集合$V$を頂点集合、集合$E$を辺集合と呼びそれぞれ$V(G)$, $E(G)$と書く。

$V(G)$の元を**頂点** (*vertex*)、 $E(G)$の元を**辺** (*edge*)と呼ぶ。

$\set{u,v}\in E(G)$を単に$uv$あるいは$vu$と書く。

グラフ$G$の頂点の数 $\abs{V}$ を**オーダー**あるいは**位数** (*order*)、辺の数 $\abs{E}$ を**サイズ**あるいは**大きさ** (*size*)と呼ぶ。$G$ のオーダーを $\abs{G}$ によりあらわし、サイズを $e(G)$ によりあらわす。

$G=(V, E)$ がオーダー$n$ のグラフであるとき、
$$0\leq \abs{E}\leq \binom{n}{2}=\frac{n(n-1)}{2}$$ 
となる。

頂点$e=uv\in E(G)$のとき、$u$と$v$は**隣接する** (*adjacent*)と言い、$u$と$e$は**接続する** (*incident*) と言う。また $e$ は $u$ と $v$ を**結ぶ** (*join*) と言い、頂点 $u$, $v$ を辺 $e$ の**端点** (*endvertex*) という。

グラフ$H$が$V(H)\subset V(G)$かつ$E(H)\subset E(G)$を満たすとき、$H$を$G$の**サブグラフ**あるいは**部分グラフ** (*subgraph*)と呼ぶ。
$V(H)=V^\p\subset V$ で、$E(H)$ が $x, y\in V^\p$ となる辺 $xy\in E(G)$ をすべて含んでいるとき、$H$ を $V^\p$ により**誘導される** (*induced*, *spanned*) 部分グラフであるといい、$G[V^\p]$ によりあらわす。

$V(G)$をどのように二つの集合$X,Y$に分割してもある$x\in X,y\in Y$が存在して$xy\in E(G)$となるとき、$G$を**連結グラフ** (*connected graph*) と呼ぶ。 

グラフ $G_1 = (V_1, E_1)$ と グラフ $G_2 = (V_2, E_2)$ が**同型** (*isomorphic*) であるとは、頂点の集合の全単射 $\psi\colon V_1\to V_2$, $x\mapsto \psi_x$ が存在し、$xy\in E_1\Longleftrightarrow \psi_x\psi_y\in E_2$ となることをいう。グラフの構造について議論するときは、同型なグラフを同一視して議論することも多い。

# 代表的なグラフ

グラフ理論の議論をする際によく表れる代表的なグラフを定義する。

任意の頂点が隣接するグラフを**完全グラフ** (*complete graph*)と呼び、オーダー$n$の完全グラフを$K_n$と書く。$\displaystyle e(K_n)=\binom{n}{2}=\frac{n(n-1)}{2}$ となる。

どの頂点も隣接しないグラフを**空グラフ** (*empty graph*)と呼び、オーダー$n$の完全グラフを$E_n$と書く。$e(E_n)=0$ となる。また、$E_1=K_1$ である。

隣り合う頂点のみが隣接するように一列に並べられるグラフをパスグラフと呼び、オーダー$n+1$のパスグラフを$P_n$と書く。$P_n$ の**長さ** (*length*)を $n$ と定める。パスグラフを単に*パス*あるいは*道* (*path*) ともいう。

隣り合う頂点のみが隣接するように円周上に並べられるグラフをサイクルグラフと呼び、オーダー$n$のサイクルグラフを$C_n$と書く。$C_n$ の長さを $n$ と定める。サイクルグラフを単に*サイクル*あるいは*閉路* (*cycle*) ともいう。$C_n$ を$n$角形ともいう。

任意の頂点の次数が等しいグラフを**正則グラフ** (*regular graph*)と呼ぶ。


グラフ

&&&exc
$G$から任意に$2$頂点を選ぶ選び方は$_nC_2$であることから明らか。等号成立は$G=K_n$のとき。
&&&

&&&exc 
a)明らか。
b)$r+s=n$なので、ある$k$が存在して$rs=\lt(\frac{n}{2}+k\rt)\lt(\frac{n}{2}-k\rt)$と書ける。
よって$m\leq rs=\lt(\frac{n}{2}+k\rt)\lt(\frac{n}{2}-k\rt)\leq\frac{n^2}{4}$。
c)等号成立は$k=0$のときなので$r=s=\frac{n}{2}$のとき。
&&&

&&&exc *
a)明らか。
b)明らか。
&&&

&&&exc
明らか。
&&&

&&&exc
$k=0$)$nK_1$
$k=1$)$nK_2$
$k=2$)各コンポーネントがサイクルグラフとなるグラフ。
&&&

&&&exc
a)各人の持つ友人は高々$n-1$人なので箱の巣原理から従う。
b)バタフライグラフ。
&&&

&&&exc
a)省略。
b)$v(Q_n)=2^n, e(Q_n)=n\cdot2^{n-1}$
c)各頂点$v=(a_1,\cdots,a_n)$に対して、$S_v=\sum_{i=1}^na_i$を考える。$X=\set{v: S_v\equiv0(\mathrm{mod}.2)}, Y=V\backslash V_2$と定めると$ Q_n=G[X,Y]$が成り立つ。
&&&

&&&exc
a)省略。
b)グラフ準同型$\varphi:Q_n\ra BL_n$を$\varphi\lt((a_1,\cdots,a_n)\rt)=\set{i:a_i\neq0}$と定めるとこれはグラフ同型を定める。よって$v(BL_n)=2^n, e(BL_n)=n\cdot2^{n-1}$。
c)$Q_n$と同型であることから明らか。
&&&

&&&exc *
a)$\sum_{v\in X}d(v)=m$, $\sum_{v\in Y}d(v)=m$より成り立つ。
b)$k|X|=\sum_{v\in X}d(v)=\sum_{v\in Y}d(v)=k|Y|$より成り立つ。 
&&&

&&&exc *
大きさが$a_i$の部集合に含まれる頂点$v$の次数は$d(v)\leq n-a_i$。
よって$2m=\sum_{v\in V}d(v)\leq \sum_{i=1}^ka_i(n-a_i)$。
&&&

&&&exc *
a)
b)
&&&

&&&exc
a)対偶を示す。$G$が非連結であるとすると、$V=X\cup Y$を満たす互いに素な集合$X$, $Y$で、$X$と$Y$の間に辺の存在しないものが存在する。
$n\geq2$, $1\leq x\leq n-1$のとき、$x^2-nx\leq1-n$が成り立つことに注意すると、$m\leq\ _{|X|}C_2+\ _{|Y|}C_2=\frac{1}{2}\set{|X|(|X|-1)+(n-|X|)(n-|X|-1)}\leq\ _{n-1}C_2$
b)$K_1+K_{n-1}$
&&&

&&&exc
a)対偶を示す。$G$が非連結であるとすると、$V=X\cup Y$を満たす互いに素な集合$X$, $Y$で、$X$と$Y$の間に辺の存在しないものが存在する。$|X|\leq\frac{n}{2}$として一般性を失わない。任意の$v\in X$に対して、$d(v)\leq\frac{n}{2}-1=\frac{1}{2}(n-2)$が成り立つ。
b)$2K_{\frac{n}{2}}$
&&&

&&&exc
$$\delta_{ij}=\left\{\begin{array}{cl}
1 & (v_iv_j\in E) \\
0 & (v_iv_j\not\in E)
\end{array}\right.$$
と定める。
$A^2$の対角成分は$a_{ii}=\sum_{j=1}^n\delta_{ij}=d(v_i)$である。
$$\mu_{ij}=\left\{\begin{array}{cl}
1 & (v_i\in e_j) \\
0 & (v_i\not\in e_j)
\end{array}\right.$$
と定める。
$MM^t$の対角成分は$m_{ii}=\sum_{j=1}^m\mu_{ij}=d(v_i)$である。
&&&

&&&exc
$G$のコンポーネントに番号を付ける。接続行列を$i_1$行目までコンポーネント$1$の頂点、$i_1+1$行目から$i_2$行目までコンポーネント$2$の頂点$\cdots$、となるように取る。$i_k$行目に$i_k+1$行目から$i_{k+1}-1$行目までを足すと各列の値は$0$となる。よって、$A$のランクは$n-1$以下かつ等号成立は$G$がコンポーネントを一つしか持たない、すなわち連結のとき。
&&&

&&&exc
a)次数列$\mathbb{d}$を持つグラフが存在するならば握手補題より$\sum_{i=1}^n d_i$は偶数。逆に、$\sum_{i=1}^n d_i$が偶数とする。$d_i$が偶数ならば$\frac{d_i}{2}$個のループを持ち、$d_i$が奇数ならば$\frac{d_i-1}{2}$個のループを持つグラフ$G$を考える。$\mathbb{d}$には奇数次数が偶数個含まれているので適当にペアを組ませる。ペア同士を辺で結ぶとこれは与えられた次数列を持つグラフとなる。
b)ある$0$を含まない次数列$\mathbb{d}$を持つグラフが存在すると仮定し、$\mathbb{d}$は$\sum_{i=1}^nd_i$が奇数であるか、$d_1>\sum_{i=2}^nd_i$を満たすとする。$\sum_{i=1}^nd_i$が奇数であるとすると握手補題と矛盾するので$d_1>\sum_{i=2}^nd_i$が成り立つ。次数$d_1$を持つ頂点を$v$とする。$v$と隣接する頂点$w$に対して$v$と$w$の間の辺の数を$k_w$とし、$k=\sum_{w\in N(v)}(k_w-1)$とおく。$d_1-k>\sum_{i=2}^nd_i-k\geq n-1$よりこれは矛盾。
逆に、列$\mathbb{d}$が$\mathbb{d}$は$\sum_{i=1}^nd_i$が偶数かつ$d_1\leq\sum_{i=2}^nd_i$を満たすとする。次数列$\mathbb{d}$を持つグラフが存在することを$|\mathbb{d}|$に関する帰納法で示す。$|\mathbb{d}|=1$のとき、$\mathbb{d}=(0)$よりこれは空グラフの次数列となる。$|\mathbb{d}|=n-1$のとき次数列$\mathbb{d}$を持つグラフが存在すると仮定する。$\mathbb{d}=(d_1,\cdots,d_n)$とする($d_n>0$)。列$\mathbb{d^\p}$を$\mathbb{d^\p}=(d_1-\min\set{d_n,d_1-d_2},d_2-1,\cdots,d_{d_n-(d_1-d_2)+1}-1,d_{d_n-(d_1-d_2)+2},\cdots,d_{n-1})$と定義すると、必要であれば$d_2$以降を並べ替えることで単調非増加列となる。$\sum_{i=1}^{n-1}d^\p_i=\sum_{i=1}^nd_i-2d_n$より$\sum_{i=1}^{n-1}d^\p_i$は偶数である。$d_n>d_1-d_2$のとき、
$$\begin{split}
d_1^\p&\leq\sum_{i=2}^nd_i+(d_1-d_2)\\
&=\sum_{i=2}^{n-1}d_i-\lt(d_n-(d_1-d_2)\rt)\\
&=\sum_{i=2}^{d_n-(d_1-d_2)+1}(d_i-1)+\sum_{d_n-(d_1-d_2)+2}^{n-1}d_i\\
&=\sum_{i=2}^{n-1}d_i^\p
\end{split}$$
が成り立つ。$d_n\leq d_1-d_2$のときも$d_1^\p\leq\sum_{i=2}^nd_i^\p$が成り立つので、帰納法の仮定から次数列$\mathbb{d^\p}$を持つグラフ$G$が存在する。$G$に対して頂点を一つ追加し、次数$d_1^\p$の頂点との間に$\min\set{d_n,d_1-d_2}$本の辺を追加し、$d_i-d_i^\p=1$を満たす頂点との間に$1$本づつ辺を追加する。以上の操作でできるグラフは次数列$\mathbb{d}$を持つグラフとなる。

&&&

&&&exc
a)$Gの次数列を\mathbb{d}=(d_1,\cdots,d_n)$とする。このとき、$\overline{G}$の次数列は$(n-1-d_n,\cdots,n-1-d_1)$
b)$G_1$, $G_2$を$G$の異なる連結成分とする。任意の$v_1\in V(G_1)$, $v_2\in V(G_2)$に対して$v_1v_2\in E(\overline{G})$が成り立つ。よって任意の$x,y\in V(G_1)$はある$z\in V(G_2)$を通るパスが存在する。よって$\overline{G}$は連結。逆は$G=K_1$が反例となる。
&&&

&&&exc (Erdős–Gallaiの定理)
a)$e(K_7)=21$なので次数和がこれより大きな次数列はグラフ的ではない。
b)$V_k=\set{v_1,\cdots,v_k}$とすると、$\sum_{i=1}^kd_i$は$G[V_k]$内の辺を二回づつ、$G[V_k]$から$G[V(G)\backslash V_k]$への辺を一回づつ数えている。$G[V_k]$のサイズは高々$_kC_2$で、任意の$v\in V(G[V(G)\backslash V_k])$から$G[V_k]$への辺の数は高々$\min\set{k,d_i}$である。以上より、$\sum_{i=1}^kd_i\leq2\ _kC_2+\sum_{i=k+1}^n\min\set{k,d_i}=k(k-1)+\sum_{i=k+1}^n\min\set{k,d_i}$
&&&

&&&exc (Havel-Hakimiの定理)
a)次数列$\mathbb{d}^\p$を持つグラフ$G$が存在すると仮定する。$G$に頂点$v$を追加し、$d_i-d_i^\p=1$となる次数を持つ頂点との間に辺を追加することで次数列$\mathbb{d}$を持つグラフが得られる。
逆に、次数列$\mathbb{d}$を持つグラフ$G$が存在すると仮定する。$v_i\in V(G)$に対して$d(v_i)=d_i$とする。グラフ$G$から2-switchを繰り返すことで$N(v_1)=\set{v_2,\cdots,v_{d_1+1}}$を満たすグラフに変形できることを示す。グラフ$G$が$N(v_1)=\set{v_2,\cdots,v_{d_1+1}}$を満たすグラフに変形できないグラフで$N(v_1)$内の頂点の添え字の総和が最小のグラフとする。ある$v_k\in N(v_1)$に対して$j<k$を満たす$v_j\not\in N(v_1)$が存在する。$j<k$なのである$v_l$が存在して$v_jv_l\in E(G)$かつ$v_kv_k\not\in E(G)$となる。$v_1v_k$, $v_jv_l$を$v_1v_j$, $v_kv_l$で取り換えるとこれは$G$の2-switchで、得られるグラフ$G^\p$は次数列$\mathbb{d}$を持つが$N_{G^\p}(v_1)$の添え字の総和は$N_G(v_1)$の添え字の総和より小さい。よってこれは矛盾。以上よりグラフ$G$から2-switchを繰り返すことで$N(v_1)=\set{v_2,\cdots,v_{d_1+1}}$を満たすグラフに変形できる。変形して得られたグラフは次数列$\mathbb{d}$を持ち、$G-{v_1}$は$\mathbb{d^\p}$を持つ。
b)与えられた$\mathbb{d}$に対して(a)の$\mathbb{d^\p}$を計算して非増加列になるように並べ替えることを繰り返す。次数列$\mathbb{d}$を持つグラフが存在するならば$\mathbb{d^{(|\mathbb{{d}}|-1)}}=(0,\cdots,0)$となる。$\mathbb{d^{(|\mathbb{{d}}|-1)}}=(0,\cdots,0)$とならない場合は$\mathbb{d}$はグラフ的ではない。$\mathbb{d^{(|\mathbb{{d}}|-1)}}=(0,\cdots,0)$となるとき、(a)の証明と同様の手順で$\mathbb{d^{(i)}}$から$\mathbb{d^{(i+1)}}$を復元することを繰り返すことで次数列$\mathbb{d}$を持つグラフが得られる。
&&&

&&&exc
距離がちょうど$1$である点対の数が最大になるように並べるには正三角形のタイルで埋め尽くすように並べれば良い。これを$n$頂点のグラフとして表す。互いに距離が$1$の頂点間を辺で結ぶとこれは平面グラフとなる。よって$m\leq 3n-6$が成り立ち、$S$の点対は$3n$個以下となる。
&&&

&&&exc

&&&

&&&exc

&&&

&&&exc

&&&

&&&exc

&&&

&&&exc

&&&


第1章第1節

&&&exc
a)明らか。
b)明らか。
&&&

&&&exc
ループを持つ頂点に隣接する頂点の次数に注目すれば同型ではないことが分かる。
&&&

&&&exc
明らか。
&&&

&&&exc
a)同型写像$\varphi$について、$\varphi(1)$の定め方は$6$通りなので、$6×3!×2!=72$より求める同型写像の個数は$72$個。
b)$72$個
&&&

&&&exc
省略。
&&&

&&&exc
省略。
&&&

&&&exc
グラフ準同型$\varphi:Q_n\ra BL_n$を$\varphi\lt((a_1,\cdots,a_n)\rt)=\set{i:a_i\neq0}$と定めるとこれはグラフ同型を定める。
&&&

&&&exc

&&&

&&&exc
明らか。
&&&

&&&exc
a)グラフ$P_n$について$d(v)=d(v^\p)=1$とする。$P_n$の自己同型は恒等写像と$\varphi(v)=v^\p$となる同型の二つ。よって$Aut(P_n)\cong S_2$である。また、グラフ$C_n$について、$\varphi_{k^+}$を$\varphi_{k^+}(0)=k$, $\varphi_{k^+}(1)=k+1(mod.n)$と定める。$\varphi_{k^-}$を$\varphi_{k^-}(0)=k$, $\varphi_{k^-}(1)=k-1(mod.n)$と定めると、$Aut(C_n)=\set{\varphi_{k^+}:0\leq k\leq n-1}\cup\set{\varphi_{k^-}:1\leq k\leq n-1}\cong D_n$である。
b)$m\neq n$のとき、$S_m\times S_n$であり、$m=n$のとき、$S_{2m}$である。
&&&

&&&exc
明らか。
&&&

&&&exc

&&&

&&&exc
a)(反射律)恒等写像を考えると$v\sim v$
(推移律)$u\sim v$, $v\sim w$のとき、$\varphi(u)=v$, $\psi(v)=w$を満たす自己同型$\varphi$, $\psi$が存在する。$\psi\circ\varphi$は自己同型で$\psi\circ\varphi(u)=w$なので$u\sim w$
(対称律)$u\sim v$のとき、$\varphi(u)=v$を満たす自己同型が存在する。$\varphi^{-1}$は自己同型で$\varphi^{-1}(v)=u$を満たすので$v\sim u$
b)省略。
&&&

&&&exc
a)省略。
b)ブルグラフの片側の角を伸ばしたグラフを考えればよい。
&&&

第1章第2節

&&&exc *
明らか。
&&&

&&&exc *
a)連結な場合を考えれば良い。$G$の次数$1$の頂点が$1$つ以下であるとすると、$2m=\sum_{i=1}^nd_i\geq2(n-1)+1=2n-1$が成り立つが、$G$はtreeなので$m=n-1$が成り立つ。よって$2(n-1)=2n-2\geq2n-1$となりこれは矛盾。
b)(a)の証明より明らか。等号成立はパスグラフのとき。
&&&

&&&exc
a)閉路を持たないならば$m\leq n-1<n$が成り立つことから明らか。
b)$P_n$
&&&

&&&exc
a)$\delta<2$ならば明らかなので、$\delta\geq2$とする。$P=v_1\cdots v_k$を$G$の最長道とする。$d(v_k)\geq\delta\geq2$なので$v_k$は$v_{k-1}$以外の近傍を$\delta-1$個以上持つ。$P$の最長性と$G$が単純であることからこれらの近傍はそれぞれ異なる$P$上の頂点と隣接するので$P$の長さは$\delta$以上である。よって$G$は長さ$\delta$の道を持つ。
b)$K_{k+1}$
&&&

&&&exc
a)
b)$K_{k+1}$
&&&

&&&exc

&&&

第2章第1節

&&&exc *
省略。
&&&

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

&&&exc *
省略。
&&&

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

&&&exc *
$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$の細分を含むことが従う。
&&&

&&&exc
省略。
&&&

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

&&&exc
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$である。
&&&

&&&exc
$\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}$が成り立つ。
&&&

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

&&&exc

&&&

&&&exc

&&&

第10章第1節

# 定義

&&&def 近傍、次数
$G=(V, E)$ をグラフとする。
- 頂点 $v\in V$ に隣接する頂点全体の集合 $\{w: vw\in E\}$ を $v$ の**近傍** (*neighborhood*) といい、$N(v)=N_G(v)$ によりあらわす。
- $N(v)$ の濃度、つまり $v$ に隣接する頂点全体の個数を頂点 $v$ の**次数** (*degree*) といい、$d(v)$ によりあらわす。これは、頂点 $v\in V$ に接続する辺の個数に一致する。
&&&
$G=(V, E)$ の**最小次数** (*minimal degree*) を $\delta(G)=\min_{v\in V} d(v)$ によりあらわし、
**最大次数** (*maximal degree*) を $\Delta(G)=\max_{v\in V} d(v)$ によりあらわす。
$\delta(G)=\Delta(G)=k$ となるとき、つまりすべての頂点の次数が $k$ であるとき $G$ を $k$-**正則グラフ** (*$k$-regular graph*) という。

&&&thm [th1]
$$\sum_{v\in G}d(v)=2e(G).$$
&&&
&&&prf
左辺は各頂点 $v\in G$ に関する、辺 $vw\in E(G)$ の個数を全て足し合わせたものである。つまり
$$\sum_{v\in G}d(v)=\sum_{v\in G}\abs{\{w: vw\in E(G)\}}$$
となる。ここで右辺の和において、各辺 $v_1 v_2\in E(G)$ は頂点 $v_1$ と $v_2$ に関する項に現れるから、右辺の和は $2e(G)$ に一致する。つまり
$$\sum_{v\in G}d(v)=\abs{\{(v_1, v_2): v_1 v_2\in E(G)\}}=\abs{\bigcup_{v_1 v_2\in E(G)}\{(v_1, v_2), (v_2, v_1)\}}=2e(G).$$
&&&
とくに、次数の総和はつねに偶数となる。また、
$$\delta(G)\leq \floor{\frac{2e(G)}{n}}, \Delta(G)\geq \ceil{\frac{2e(G)}{n}}$$
となる。

近傍と次数

&&&exc
a)グラフが平面的ならば明らかに各ブロックは平面的である。逆に各ブロックが平面的なグラフは、各ブロックが$K_{5}$と$K_{3,3}$をminorとして含まない。命題5.1(a)より任意の二つのブロックは高々一つの頂点しか共有しないので各ブロックが平面的ならばそのグラフは$K_{5}$と$K_{3,3}$をminorとして含まない。
b)極小な非平面的グラフは$K_5$と$K_{3,3}$なので主張は明らか。
&&&

&&&exc *

&&&

第10章第2節

&&&exc
$G$の平面描画から交差する辺を取り除いたグラフ$G^\p$は平面グラフである。よって$m-cr(G)\leq 3n-6$が成り立つ。
&&&

&&&exc
a)$G$の平面描画の面の数を$f$とする。girth $k$より$2m\geq kf$が成り立つ。Eulerの公式を代入すると$2m\geq k(2-n+m)$なので、これを変形すると$m\leq\frac{k(n-2)}{k-2}$
b)Pertersen graphはgirth $5$なので(a)の式に代入すれば非平面的であることが分かる。
&&&

&&&exc

&&&

&&&exc
a)位数$11$以上のグラフ$G$が平面的であるとすると、$m\leq3n-6$を満たす。$e(\overline{G})=\frac{n(n-1)}{2}-m$であり、$\frac{n(n-1)}{2}-m-3n+6\geq\frac{1}{2}(n^2-13n+24)>0$なので$\overline{G}$は非平面的。
b)省略。($K_4$を二つ並べて間に辺を付け加えたグラフを考えれば良い。)
&&&

&&&exc
a)面の次数を$r$とすると、$2m=rf$であり、頂点の次数を$r^\p$とすると、$2m=r^\p n$である。これらをEulerの公式に代入すると、$n-\frac{r^\p n}{2}+\frac{r^\p n}{r}=2$が成り立つ。これを整理すると、$n=\frac{4r}{2r+2r^\p-rr^\p}$
b)平面グラフは次数$5$以下の頂点と次数$5$以下の面を共に少なくとも一つ以上持つので、$3\leq r,r^\p\leq5$を(a)で求めた式に代入すれば良い。
$r$, $r^\p$の組み合わせは全部で$6$通りだが$r=r^\p=4$の場合はこれを満たす$n$が存在しないので全部で$5$通りである。
&&&

&&&exc
a)極大平面グラフでは$m=3n-6$が成り立つので、できる限り多く極大平面グラフができるような埋め込みを考えると$\theta(G)\geq\lceil\frac{m}{3n-6}\rceil$が成り立つ。
b)$\frac{\frac{n(n-1)}{2}}{3n-6}=\frac{n+1}{6}+\frac{1}{3(n-2)}$なので、$\theta(G)\geq\lfloor\frac{n+1}{6}\rfloor+1$
c)省略。
d)(c)より$T_{6,12}$は高々$2$枚の平面に埋め込める。$e(T_{6,12})=60$, $e(K_{12})=66$なので$K_{12}$は高々$3$枚の平面に埋め込める。(b)より$\theta(K_{12})\geq3$なので$\theta(K_{12})=3$である。
&&&

&&&exc
a)$G$はgirth $4$なので、平面グラフならば$m\leq2n-4$が成り立つ。よって問題6と同様にして$\theta(G)\geq\lceil\frac{m}{2n-4}\rceil$
b)(a)の式に$v(K_{m,n})=m+n$, $e(K_{m,n})=mn$を代入すると、$\theta(K_{m,n})\geq\lceil\frac{mn}{2n+2n-4}\rceil$
&&&

&&&exc
a)ⅰ)$G^\ast$にEulerの公式を適用すると、$v(G^\ast)-e(G^\ast)+f(G^\ast)=2$である。$G$は自己双対グラフなので$v(G^\ast)=v(G)$が成り立つ。これと双対の定義から導かれれる$e(G^\ast)=e(G)$と$f(G^\ast)=v(G)$を代入すると、$e(G)=2v(G)-2$が得られる。
ⅱ)省略。(実際に双対を書いて数えればよい。)
b)省略。
&&&

&&&exc

&&&

&&&exc

&&&

第10章第3節

グラフ $G=(V, E)$ 上の長さ $n$ のパスとは、$G$ の相異なる $n+1$ 個の頂点を通る辺 $v_0 v_1, \ldots, v_{n-1} v_n$ からなるパスをいい、グラフ $G=(V, E)$ 上の長さ $n$ のサイクルとは、$G$ の相異なる $n$ 個の頂点を通る辺 $v_0 v_1, \ldots, v_{n-2} v_{n-1}, v_{n-1} v_0$ からなるサイクルをいう。

# 一般化

パスとサイクルについて、より一般的な概念も定義される。

&&&def 歩道、小道、閉歩道
- グラフ $G = (V, E)$ について、$G$ の**歩道** (*walk*) とは、$V$ の(異ならなくともよい)頂点 $v_0, v_1, \ldots v_\ell$ と $E$ の辺 $e_1=v_0 v_1, e_2=v_1 v_2, \ldots, e_\ell=e_{\ell -1} e_\ell$、つまり $e_i$ が $v_{i-1}$ と $v_i$ をつなぐようなものの組のことをいう。このとき、この歩道は $v_0$ と $v_\ell$ を結ぶという。$\ell$ を、この歩道の**長さ** (*length*) という。
- グラフ $G = (V, E)$ について、$G$ の**小道** (*trail*) とは、$V$ の歩道のうち、辺 $e_1, \ldots, e_\ell$ が相異なるものをいう（$v_i$ は相異ならなくてもよい。つまり同じ頂点を複数回通ってもよい）。$\ell$ を、この小道の長さという。
- グラフ $G = (V, E)$ について、$G$ の**閉歩道** (*circuit*) とは、$V$ の小道のうち、$v_0=v_\ell$ となるものをいう。つまり (異ならなくともよい)頂点 $v_1, v_2, \ldots v_\ell$ と $E$ の異なる辺 $e_1=v_1 v_2, \ldots, e_{\ell -1}=v_{\ell-1} v_\ell, e_\ell=v_\ell v_1$、つまり $1 \leq i \leq \ell-1$ について $e_i$ が $v_i$ と $v_{i+1}$ をつなぎ、$e_\ell$ が $v_\ell$ と $v_1$ をつなぐようなものの組のことをいう。$\ell$ を、この閉歩道の長さという。
&&&

$G$ の小道のうち、頂点が $v_0, v_1, \ldots v_\ell$ が相異なるものが $G$ 上のパスとなる。また、$V$ の閉歩道のうち、$v_1, \ldots, v_\ell$ が相異なるものが $G$ 上のサイクルとなる。

$2$頂点 $u$, $v$ を結ぶ長さ $n$ の歩道が存在するとき、$u$, $v$ を結ぶ長さ $n$ 以下のパスが存在する。実際、$u$, $v$ を結ぶ長さ $n$ の歩道 $u=u_0, \ldots, u_n=v$ について、$u_i=u_j$ となる $i<j$ があるとき、$u_{i+1}, \ldots, u_{j-1}$ を取り除くことで、$u$, $v$ を結ぶ、長さが $n$ より小さい歩道ができる。これを繰り返すことで、$u$, $v$ を結ぶ長さ $n$ 以下のパスが必ずとれる。同様にして、$2$頂点 $u$, $v$ を結ぶ長さ $n$ の閉歩道が存在するとき、$u$, $v$ を結ぶ長さ $n$ 以下のサイクルが存在する。

# サイクルに関する古典的な定理
サイクルについて、つぎのような事実が知られている。

&&&thm Veblenの定理 (1912) [th1]
グラフ $G = (V, E)$ の辺がサイクルに分割される $\Longleftrightarrow$ $G$ の各頂点の次数が偶数。
&&&
&&&prf
$E$ がサイクルに分割されているとする。サイクルの各頂点は次数 $2$ をもつから、各頂点 $v$ に接続する辺が $k_v$ 個のサイクルに分割されているとき、$d(v)=2k_v$ は偶数となる。

逆に、$G$ の各頂点の次数が偶数であるとき、グラフ $G = (V, E)$ の辺がサイクルに分割されることを、$e(G)$ に関する帰納法で示す。

$e(G)=0$ のときは、$0$ 個のサイクルに分割されていると考えることができる。
$e(G)>0$ とする。$G$ に含まれるパスで長さが最大のものをとり、それを $v_0, v_1, \ldots, v_\ell$ とおく。
$d(v_0)>0$ なので、仮定より $d(v_0)\geq 2$ となるから $v_1$ 以外に $v_0$ に隣接する頂点 $w$ がとれる。$w$ が $v_2, \ldots, v_\ell$ に含まれないとすると、$w, v_0, \ldots, v_\ell$ が $G$ に含まれるパスとなってしまうが、これは $v_0, v_1, \ldots, v_\ell$ が $G$ に含まれる最長のパスであることに反する。
よって、$w$ は $v_2, \ldots, v_\ell$ のいずれかと一致する。$w=v_s$ とおくと、$v_0, \ldots, v_s$ は $G$ に含まれるサイクルとなる。
$E$ から辺 $v_0 v_1, \ldots, v_{s-1} v_s, v_s v_0$ を取り除いたグラフを $H$ とおく。$v$ が $v_0, \ldots, v_s$ のいずれとも一致しないとき $N_H(v)=N_G(v)$ となる。つまり $v$ に接続する $G$ の辺は $H$ の辺のままである。よって $d_H(v)=d_G(v)$ となる。
一方、$v=v_i$ が $v_0, \ldots, v_s$ のいずれかであるとき、$N_H(v_i)=N_G(v_i)\setminus \{v_{i-1}, v_{i+1}\}$ （ただし $v_{s+1}=v_0$ とする）となるから、$d_H(v)=d_G(v)-2$ となる。
よって、$H$ の各頂点の次数も偶数であるから、帰納法の仮定より、$H$ の辺はサイクルに分割される。したがって、$G$ の辺は、$H$ の辺のサイクルへの分割に、サイクル $v_0, \ldots, v_s$ を加えたものに分割される。
&&&

&&&thm Mantelの定理 (1907) [th2]
$\abs{G}=n$ かつ、$e(G)>\floor{n^2/4}$ となるグラフは三角形を部分グラフにもつ。言い換えれば、三角形を部分グラフにもたない位数 $n$ のグラフの大きさは $\floor{n^2/4}$ 以下である。
&&&
&&&prf
$G$ が三角形を部分グラフにもたないグラフとする。このとき、$xy\in E$ ならば $x$ と $y$ の両方に隣接する頂点は存在しないから、
$$d(x)+d(y)\leq n$$
となる。すべての辺 $xy\in E$ について、これを加えると、
$$\sum_{xy\in E}d(x)+d(y)\leq n e(G)$$
となる。一方、各 $x\in E$ について、左辺の和にあらわれる $d(x)$ の回数は、$x$ の次数に等しい。つまり
$$\sum_{xy\in E}d(x)+d(y)=\sum_{x\in V}\sum_{y\in N(x)}d(x)=\sum_{x\in V}d(x)^2$$
となる。よって
$$\sum_{x\in V}d(x)^2\leq n e(G)$$
となる。[次数に関する定理1](/glossaries/GgZ9Qs5vQVt5yl9mD4OD#th1)より、
$$\sum_{x\in V}d(x)=2e(G)$$
となるから、Cauchyの不等式より
$$(2e(G))^2=\left(\sum_{x\in V}d(x)\right)^2\leq n\sum_{x\in V}d(x)^2\leq n^2 e(G)$$
が成り立つ。それで
$$e(G)\leq n^2/4$$
となる、$e(G)$ は整数だから
$$e(G)\leq\floor{n^2/4}$$
でなければならないことがわかる。
&&&

パスとサイクル

グラフ $G = (V,E)$ の$2$頂点 $v$, $w\in V$ の**距離** (*distance*) とは、$v$ と $w$ を結ぶ道の長さの最小値をいい、$d(v, w)$ によりあらわす。
$v$ と $w$ を結ぶ道が存在しないときは $d(v, w)=\infty$ と定める。
与えられた頂点 $v\in V$ について、$v$ と他の頂点の距離 $d(v, w) ~ (w\in V)$ の最大値を $G$ の $v$-半径といい、
$$\rad (G, v)=\max_{w\in V} d(v, w)$$
によりあらわす。

$v$-半径の最小値を $G$ の**半径** (*radius*) といい、
$$\rad (G)=\min_{v\in V} \rad(G, v)=\min_{v\in V}\max_{w\in V} d(v, w)$$
によりあらわす。
$v$-半径の最大値、つまりあらゆる$2$頂点 $v, ~ w\in V$ に関する $d(v, w)$ の最大値を $G$ の**直径** (*diameter*) といい、
$$\diam (G)=\max_{v\in V} \rad(G, v)=\max_{v, ~ w\in V} d(v, w)$$
によりあらわす。

&&&ex
完全グラフ $K_n$ においては、異なる$2$頂点間の距離はつねに $1$ となるので、半径、直径はともに $1$ となる。
&&&

# 性質
通常の距離空間と同様に、グラフの距離については三角不等式が成り立つ。
&&&thm [thm1]
$u, v, w\in V$ について、つねに
$$d(u, w)\leq d(u, v)+d(v, w)$$
が成り立つ。
&&&
&&&prf
$m=d(u, v)$ とおいて、$u$ と $v$ を結ぶ最短の道をひとつとり、
$$u_0=u, u_1, \ldots, u_m=v$$ とおく。
同様に、$n=d(u, v)$ とおいて、$w$ と $v$ を結ぶ最短の道をひとつとり、$$w_0=w, w_1, \ldots, w_n=v$$ とおく。
$u_i=w_j$ となる $j$ が存在する $i$ で最小のものをとり（$u_m=w_n=v$ だから、このような $i$ は少なくともひとつ存在する）、これを $s$ とおく。
さらに $u_s=w_j$ となる $j$ をひとつとり、これを $t$ とおく。
このとき、$0\leq i\leq s-1$, $0\leq j\leq t-1$ の範囲には $u_i=w_j$ となる $i$, $j$ は存在しないから
$$u=u_0, u_1, \ldots, u_s=w_t, w_{t-1}, \ldots, w_0=w$$ 
は $u, w$ を結ぶ道となるので、
$$d(u, w)\leq s+t\leq d(u, v)+d(v, w)$$
が成り立つ。
&&&

距離


$\newcommand{\cG}{\mathcal{G}}$

#グラフマイナーの定義

任意に$e=uv\in E(G)$を取る。グラフ$G$から$e$を取り除いて$u$と$v$を同一視し、これによって発生する多重辺を同一視して一つの辺とみなす操作を辺の縮約と言う。$G$から$e$を縮約したグラフを$G/e$と書く。

辺の縮約と部分グラフを取る操作を総称してマイナー操作と呼ぶ。グラフ$G$からマイナー操作のみでグラフ$H$に到達できるとき、グラフ$H$はグラフ$G$のマイナーであると言い、$H\leq G$と書く。

マイナー関係はグラフ全体に半順序を定める。

グラフの集合$\cG$がマイナーについて閉じているとは、任意の$G\in\cG$と$G$のマイナー$H$に対して$H\in\cG$となることである。

有限個のグラフ$X_1,\cdots,X_n$に対して、どのグラフもマイナーとして含まないグラフの全体を$F(X_1,\cdots,X_n)$と書き、$X_1,\cdots,X_n$を禁止マイナーと呼ぶ。

&&&thm
$\cG$がマイナーについて閉じていることと、ある有限個のグラフ$X_1,\cdots,X_n$が存在して$\cG=F(X_1,\cdots,X_n)$となることは同値。
&&&

グラフマイナー

&&&exc (Chvátal graph)
省略。（wikiに載っている。）
&&&

&&&exc *
あるブロックを$\chi(B)$で彩色する。その後$B$と頂点を共有するほかのブロックを共有する頂点のcolorが同じになるように彩色する。任意の二つのブロックは高々一つの頂点しか共有せず、これは切断点となっているので、この方法で矛盾なく彩色できる。
&&&

&&&exc *
a)ある色$c$が他のすべての色と隣接する頂点を持たないとする。このとき$c$で塗られた頂点を隣接する頂点に存在しない色でrecoloringすると、これは$(k-1)$-coloringとなるので矛盾。
b)色$c$が塗られた頂点の近傍に$c$以外の色がすべて現れるためには次数$k-1$以上必要である。よって(a)から次数$k-1$以上の頂点を$k$個以上持つ。
&&&

&&&exc

&&&

第14章第1節

# 定義
グラフ $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$ を結ぶ道の長さも偶数でなければならない。

二部グラフはつぎのように特徴づけられる。

&&&thm [th1]
グラフ $G=(V, E)$ が二部グラフであるための必要十分条件は、$G$ が長さが奇数のサイクルをもたないことである。
&&&
&&&prf
$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$ からなる二部グラフとなる。
&&&


二部グラフ

グラフ理論について基礎的な内容を解説する。