第1章第1節

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

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}$のとき。

a)明らか。
b)明らか。

明らか。

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

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

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]$が成り立つ。

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$と同型であることから明らか。

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|$より成り立つ。

大きさが$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)$。

a)
b)

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}$

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}}$

$$\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)$である。

$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$がコンポーネントを一つしか持たない、すなわち連結のとき。

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}$を持つグラフとなる。

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$が反例となる。

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}$

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}$を持つグラフが得られる。

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