強連結成分

1：$\rightsquigarrow$ は反射的（長さ $0$ の有向歩道）かつ推移的（$u$ から $v$ への有向歩道と $v$ から $w$ への有向歩道をつなぐ）である。よって $\sim$ は反射的かつ推移的で、定義から対称的なので同値関係である。
2：$u=v_0,v_1,\dots,v_\ell=v$ を有向歩道とする。各 $i$ について、$v_0,\dots,v_i$ により $u\rightsquigarrow v_i$ であり、$v_i,\dots,v_\ell$ に $v\rightsquigarrow u$ を与える有向歩道をつなげて $v_i\rightsquigarrow u$ である。よって $v_i\sim u$、すなわち $v_i\in C$ である。したがって各有向辺 $(v_{i-1},v_i)$ は $A\cap(C\times C)$ に属し、この有向歩道は $D[C]$ の有向歩道である。$C\neq\emptyset$ とあわせて $D[C]$ は強連結である。
3：$H=(W,B)$ を強連結な部分有向グラフとする。$W$ の 2 頂点は $H$ の中で、したがって $D$ の中で互いに到達可能なので、$W$ はある同値類 $C$ に含まれ、$H\subset D[C]$ である。2 により $D[C]$ は強連結なので、極大な $H$ は $D[C]$ に等しい。逆に $D[C]$ を含む強連結な部分有向グラフ $H$ は、同じ理由である同値類 $C'$ について $D[C]\subset H\subset D[C']$ を満たし、$C\cap C'\neq\emptyset$ から $C=C'$ となって $H=D[C]$ である。よって $D[C]$ は極大である。
4：強連結なら $V\neq\emptyset$ で、任意の 2 頂点が $\sim$ の関係にあるので、同値類は $V$ だけである。逆に同値類が 1 つだけなら、それは空でない $V$ であり、任意の $u,v$ について $u\rightsquigarrow v$ である。$\square$

必要性：$D$ を強連結とし、$S$ を条件のとおりにとる。$u\in S$、$v\in V\setminus S$ をとり、$u$ から $v$ への有向歩道 $u=v_0,\dots,v_\ell=v$ をとる。$v_0\in S$、$v_\ell\notin S$ なので、$v_{i-1}\in S$、$v_i\notin S$ となる $i$ があり、$(v_{i-1},v_i)$ が求める有向辺である。
十分性：$u\in V$ を任意にとり、$u$ から到達可能な頂点の集合を $R$ とする。$u\in R$ なので $R\neq\emptyset$ である。$x\in R$、$(x,y)\in A$ なら、$u$ から $x$ への有向歩道に $y$ をつなげて $y\in R$ となるので、$R$ から外へ出る有向辺はない。条件により $R\subsetneq V$ ではありえないので $R=V$ である。$u$ は任意だったので $D$ は強連結である。$\square$

凝縮はループをもたないので、長さ $1$ の有向閉路はない。長さ $\ell\ge2$ の有向閉路 $C_0,C_1,\dots,C_\ell=C_0$ があったとする。各 $i=1,\dots,\ell$ について有向辺 $(u_i,w_i)\in A$（$u_i\in C_{i-1}$、$w_i\in C_i$）をとる。$w_i$ と $u_{i+1}$ はともに $C_i$ に属するので $w_i\rightsquigarrow u_{i+1}$ である（添字 $\ell+1$ は $1$ と読む）。これらをつなぐと
$$ u_1\to w_1\rightsquigarrow u_2\to w_2\rightsquigarrow\cdots\rightsquigarrow u_\ell\to w_\ell\rightsquigarrow u_1 $$
（$\to$ は有向辺）という閉じた有向歩道が得られ、$u_1\in C_0$ と $w_1\in C_1$ は互いに到達可能である。よって $C_0=C_1$ となり、凝縮の有向辺 $(C_0,C_1)$ が相異なる成分を結ぶことに反する。$\square$

凝縮は空でない有限の有向グラフで、thm-scc-condensation により有向閉路をもたないので、有向グラフ の記事の補題「入次数が 0 の頂点の存在」により入次数 $0$ の頂点 $C$ をもつ。これが湧き出し成分である。凝縮の有向辺の向きをすべて逆にしたものも有向閉路をもたないので、同じ補題により入次数 $0$ の頂点をもち、それはもとの凝縮で出次数 $0$、すなわち吸い込み成分である。$\square$

凝縮 $D/{\sim}$ は $k$ 頂点の有限有向グラフで、thm-scc-condensation により有向閉路をもたない。有向グラフ の記事の定理「非巡回性と位相的順序」により、凝縮の頂点を $C_1,\dots,C_k$ と並べて、凝縮のどの有向辺 $(C_i,C_j)$ でも $i< j$ となるようにできる。$D$ の有向辺 $(u,v)$ で $u\in C_i$、$v\in C_j$、$i\neq j$ なら $(C_i,C_j)$ は凝縮の有向辺なので $i< j$ である。
頂点を成分ごとにまとめて並べると、隣接行列の $(i,j)$ ブロックは $C_i$ の頂点から $C_j$ の頂点への有向辺を記録する。$i>j$ ならそのような有向辺はないので $(i,j)$ ブロックは零行列であり、$i=j$ なら $(i,i)$ ブロックは $A\cap(C_i\times C_i)$ を記録するので $D[C_i]$ の隣接行列である。$\square$

必要性：$D$ を $G$ の強連結な向き付けとする。$D$ の有向歩道は向きを忘れると $G$ の歩道なので、$G$ は連結である。$G$ が橋 $e=\{u,v\}$ をもち、$D$ で $(u,v)$ と向き付けられているとする。$G-e$ で $u$ と $v$ は異なる連結成分に属する。$u$ と $v$ が $G-e$ で道で結ばれていれば、$G$ の歩道の中で $e$ を通る部分をその道に置き換えられるので、$G$ と $G-e$ の連結成分は同じになり、$e$ が橋であることに反するからである。$G-e$ で $v$ を含む連結成分の頂点集合を $S$ とすると、$v\in S$、$u\notin S$ である。$G$ の辺で一方の端点が $S$ に、他方が $S$ の外にあるものは $e$ だけである（ほかの辺は $G-e$ の辺なので、$S$ の外へは出ない）。$e$ は $(u,v)$ と向き付けられて $S$ に入るので、$S$ から外へ出る $D$ の有向辺はない。prop-scc-cut により $D$ は強連結でなく、矛盾する。
十分性：$G$ を連結で橋をもたないとする。$|V|=1$ なら辺はなく、$G$ 自身（辺のない向き付け）が強連結である。$|V|\ge2$ とすると、連結なので辺があり、閉路 の記事の定理「閉路に含まれる辺と橋」により、橋でない辺はどれもある閉路に含まれる。
頂点集合 $W\subset V$ と、両端点が $W$ に属するいくつかの辺に向きを付けた強連結な有向グラフ $H$（頂点集合 $W$）を、$W=V$ となるまで次のように大きくしていく。最初に閉路 $z_0,z_1,\dots,z_{\ell}=z_0$ を 1 つとり、$(z_{i-1},z_i)$ と向き付けた有向閉路を $H$ とする。これは強連結である。
$W\neq V$ とする。$G$ は連結なので、一方の端点 $u$ が $W$ に、他方の端点 $v$ が $W$ の外にある辺 $\{u,v\}$ がある。この辺は閉路に含まれるので、閉路 $u=z_0,v=z_1,z_2,\dots,z_\ell=u$ をとる。$z_\ell=u\in W$ なので、$z_j\in W$ となる最小の $j\ge1$ がとれ、$z_1=v\notin W$ から $j\ge2$ である。$z_1,\dots,z_{j-1}$ は $W$ の外の相異なる頂点である。辺 $\{z_{i-1},z_i\}$（$i=1,\dots,j$）は、端点 $z_1,\dots,z_{j-1}$ のどれかを含むので $H$ の辺ではない。これらを $(z_{i-1},z_i)$ と向き付けて $H$ に加え、$W$ に $z_1,\dots,z_{j-1}$ を加える。新しい $H$ は強連結である。$W$ の頂点 $x$ からは $H$ の中で $u$ へ行き、$u\to z_1\to\cdots\to z_i$ と進めて $z_i$ に到達でき、$z_i$ からは $z_{i+1},\dots,z_j$ と進んで $z_j\in W$ に着き、そこから $W$ のどの頂点へも行けるからである。
$W$ は真に大きくなるので、有限回で $W=V$ となる。最後に、まだ向きの付いていない辺に任意に向きを付ける。有向辺を加えても到達可能性は失われないので、得られた $G$ の向き付けは強連結である。$\square$