連結グラフ

$H$ は連結なので $V(H)\neq\emptyset$ である。$H$ の 2 頂点 $x,y$ を結ぶ $H$ の道は $G$ の道でもあるので $x\sim y$ である。よって $V(H)$ はある 1 つの同値類 $C$ に含まれ、$H$ の辺は両端点が $C$ に属する $G$ の辺なので $E(H)\subset E\cap[C]^2$、すなわち $H\subset G[C]$ である。
$G[C]$ は連結である（グラフ の記事の命題「連結成分への分解」）。$G[C]\subset H$ となる連結な部分グラフ $H$ をとると、前段より $H\subset G[C']$ となる同値類 $C'$ があり、$C\subset V(H)\subset C'$ から $C=C'$、よって $H=G[C]$ である。ゆえに $G[C]$ は極大である。逆に $H$ が極大な連結部分グラフなら、前段より $H\subset G[C]$ で $G[C]$ も連結なので、極大性から $H=G[C]$ である。$\square$

1 ⇒ 2：$u\in S$、$v\in V\setminus S$ をとり、$u$ と $v$ を結ぶ道 $u=v_0,v_1,\dots,v_\ell=v$ をとる。$v_0\in S$、$v_\ell\notin S$ なので、$v_i\notin S$ となる最小の $i$ があり、$i\ge1$ である。このとき $v_{i-1}\in S$、$v_i\notin S$ なので、辺 $v_{i-1}v_i$ は $E(S,V\setminus S)$ に属する。
2 ⇒ 1：頂点 $r\in V$ を 1 つ固定し、$r$ と道で結ばれる頂点全体を $R$ とする。長さ $0$ の道により $r\in R$ である。$R\neq V$ と仮定すると、$S=R$ は $\emptyset\neq S\subsetneq V$ を満たすので、2 により辺 $xy$ で $x\in R$、$y\notin R$ となるものがある。$r$ と $x$ を結ぶ道の後に $y$ を付け加えると $r$ と $y$ を結ぶ歩道になり、そこから $r$ と $y$ を結ぶ道が取り出せるので $y\in R$ となり、矛盾する。よって $R=V$ である。任意の $u,v\in V$ は $u\sim r$、$r\sim v$ なので、推移性により $u\sim v$ であり、$G$ は連結である。$\square$

要点：$G+uv$ の道は、辺 $uv$ を使わなければ $G$ の道であり、使うなら $uv$ の前後で $G$ の道 2 本に分かれる。したがって新しく結ばれるのは $[u]$ の頂点と $[v]$ の頂点だけである。

$E$ の元を $e_1,\dots,e_m$（$m=|E|$）と並べ、$G_0:=(V,\emptyset)$、$G_k:=G_{k-1}+e_k$ とおく。$G_0$ の連結成分は $n$ 個の孤立点であり、$G_m=G$ である。lem-connected-graph-add-edge により各段階で連結成分の個数は $1$ 減るか変わらないので、$c=c(G_m)\ge n-m$、すなわち $m\ge n-c$ である。
等号 $m=n-c$ は、すべての段階で連結成分の個数が $1$ 減ること、すなわち各 $e_k=u_kv_k$ の端点が $G_{k-1}$ の異なる同値類に属することと同値である。ある段階で $u_k$ と $v_k$ が $G_{k-1}$ の同じ同値類に属したとすると、$G_{k-1}$ に $u_k$ と $v_k$ を結ぶ道 $P$ がある。$e_k$ は $G_{k-1}$ の辺でないので $P$ の長さは $2$ 以上であり、$P$ の後に辺 $e_k$ で $u_k$ に戻る閉歩道は、$G$ の長さ $3$ 以上の閉路である。逆に $G$ が閉路 $Z$ をもつとし、$Z$ の辺のうち番号が最大のものを $e_k$ とする。$Z$ から $e_k$ を除いた残りは $G_{k-1}$ の中の $u_k$ と $v_k$ を結ぶ道なので、この段階で連結成分の個数は減らない。以上から、等号が成り立つことと $G$ が閉路をもたないことは同値である。2 は 1 で $c=1$ とした場合である。$\square$

1：$G$ が連結でないとすると、prop-connected-graph-cut により $\emptyset\neq S\subsetneq V$ で $E(S,V\setminus S)=\emptyset$ となる $S$ がある。$s=|S|$、$t=n-s$ とおくと $s,t\ge1$ であり、すべての辺は $S$ の中か $V\setminus S$ の中にあるので
$$ |E|\le\binom{s}{2}+\binom{t}{2}=\binom{n}{2}-st . $$
$st-(n-1)=st-s-t+1=(s-1)(t-1)\ge0$ なので $|E|\le\binom{n}{2}-(n-1)=\binom{n-1}{2}$ となり、仮定に反する。
2：$u\neq v$ が隣接しないとする。単純グラフなので $N(u)$ と $N(v)$ はともに $V\setminus\{u,v\}$ に含まれ（$u\notin N(u)$、$v\notin N(u)$）、$|N(u)|+|N(v)|\ge2\delta(G)\ge n-1>n-2=|V\setminus\{u,v\}|$ なので、$N(u)\cap N(v)\neq\emptyset$ である。その元 $w$ により $u,w,v$ は長さ $2$ の道である。よって任意の 2 頂点の距離は $2$ 以下で、$G$ は連結である。
3：$G$ が連結でないとし、相異なる $u,v\in V$ をとる。$u$ と $v$ が $G$ の異なる連結成分に属するなら、$uv\notin E$ なので $uv$ は $\overline G$ の辺である。同じ連結成分 $C$ に属するなら、$G$ は連結でないので $C$ の外の頂点 $w$ があり、異なる連結成分の頂点を結ぶ $G$ の辺はないので、$uw$ と $wv$ はともに $\overline G$ の辺である。よって $\overline G$ で相異なる 2 頂点の距離は $2$ 以下であり、$n\ge1$ とあわせて $\overline G$ は連結である。$\square$

$S^{-1}=S$ なので、部分群 の記事の命題「生成される部分群の元の記述」により、$\langle S\rangle$ は $S$ の元の有限個の積 $s_1s_2\cdots s_k$（$k\ge0$、$k=0$ は $1$）全体である。
$g$ から $h$ への歩道 $g=g_0,g_1,\dots,g_k=h$ があるとする。各 $i$ で $g_{i-1}^{-1}g_i\in S$ なので、$s_i:=g_{i-1}^{-1}g_i$ とおくと $h=gs_1s_2\cdots s_k\in g\langle S\rangle$ である。逆に $h=gs_1\cdots s_k$（$s_i\in S$）なら、$g,\ gs_1,\ gs_1s_2,\ \dots,\ gs_1\cdots s_k=h$ は隣り合う頂点が隣接する歩道である。よって $g$ と $h$ が歩道（したがって道）で結ばれることは $h\in g\langle S\rangle$ と同値であり、$g$ を含む同値類は $g\langle S\rangle$ である。
$\Gamma\neq\emptyset$（$1\in\Gamma$）なので、連結であることは同値類が $1$ 個であること、すなわち $1\cdot\langle S\rangle=\Gamma$ と同値である。連結成分は左剰余類と 1 対 1 に対応するので（群 の記事の命題「左剰余類は同値類である」）、その個数は左剰余類の個数 $[\Gamma:\langle S\rangle]$ である。$\square$