深さ優先探索

要点：訪問は入れ子に行われ、時刻 $\mathrm{pre}(v)$ に進行中の訪問はちょうど $v$ の真の先祖の訪問である。

$\mathrm{pre}(u)<\mathrm{pre}(v)$ としてよい。時刻 $\mathrm{pre}(u)$ には $v$ に印が付いていない。$u$ の訪問は、終わる前に $u$ のすべての隣接頂点を見るので、$v$ も見る。そのとき $v$ に印が付いていなければ、$p(v)=u$ となり $u$ は $v$ の親である。すでに印が付いていれば、$v$ は時刻 $\mathrm{pre}(u)$ より後、$u$ の訪問が終わる前に発見されているので $\mathrm{pre}(u)<\mathrm{pre}(v)<\mathrm{post}(u)$ であり、lem-dfs-parenthesis の 3 ⇒ 1 により $u$ は $v$ の真の先祖である。どちらの場合も $u$ は $v$ の先祖である。$\square$

thm-dfs-no-cross により、どの辺も深さ優先探索森の同じ木の 2 頂点を結ぶので、$G$ が連結なら森は $r$ を根とする 1 本の木で、すべての頂点を含む。とくに $r$ は子をもつ。$r$ の子が $c_1$ だけなら、$T_{c_1}$ は $r$ 以外のすべての頂点を含む木なので、$r$ を除いても連結である。子が $c_1,c_2,\dots$（2 個以上）なら、$T_{c_1}$ の頂点と $T_{c_2}$ の頂点を結ぶ辺はない。そのような辺があれば、thm-dfs-no-cross により一方が他方の先祖になるが、$T_{c_1}$ と $T_{c_2}$ は先祖・子孫の関係で結ばれない（共通の先祖は $r$ だけ）からである。$T_{c_1}$ の頂点 $x$ から出る辺の他端は、同じ定理により $x$ の先祖か子孫であり、$T_{c_1}$ の中にあるか $r$ である。よって $r$ を除くと、$T_{c_1}$ の頂点からほかの頂点へ行く道はなく、連結でない。$\square$

準備として、$T_v$ の頂点 $x$ とその外の頂点 $w$ を結ぶ辺 $f=xw$ で $f\ne e$ のものは、木に入らない辺で、$w$ は $v$ の真の先祖であることを示す。木の辺は頂点と親を結ぶが、$x\ne v$ なら $p(x)\in T_v$、$x$ の子も $T_v$ に属するので、$T_v$ の内と外を結ぶ木の辺は $e$ だけである。よって $f$ は木に入らない。thm-dfs-no-cross により $w$ は $x$ の先祖か子孫で、$x$ の子孫は $T_v$ に属するから $w$ は $x$ の先祖である。$x$ の先祖は $x$ から親をたどって $v$ を経て根に至る列の頂点で、$w\notin T_v$ なので $w$ は $v$ の真の先祖である。
また、$T_v$ の頂点 $x$ は $v$ の子孫なので、lem-dfs-parenthesis により $\mathrm{pre}(x)\ge\mathrm{pre}(v)$ であり、$v$ の真の先祖 $w$ については $\mathrm{pre}(w)<\mathrm{pre}(v)$ である。
1：木に入らない辺 $xw$ は、thm-dfs-no-cross により一方（$w$ とする）が他方の真の先祖である。$w=p(x)$ なら $xw$ は木の辺になってしまうので、$w$ は $x$ から親を 2 回以上たどった先にある。木の中の $w$ から $x$ への道（長さ $2$ 以上）に辺 $xw$ を加えると閉路になるので、$xw$ は橋でない。
2：(i) ⇒ (ii)：$e$ のほかに $T_v$ の内と外を結ぶ辺 $f=xw$（$x\in T_v$）があったとする。準備により $w$ は $v$ の真の先祖である。木の中の $w$ から $p(v)$ への道、辺 $e$、木の中の $v$ から $x$ への道、辺 $f$ をつなぐと、$w$ に戻る閉じた歩道で、頂点は重複しない（前半は $v$ の真の先祖、後半は $T_v$ の頂点）。長さは $3$ 以上である（$w=p(v)$ なら $f\ne e$ より $x\ne v$ で、$v$ から $x$ への道の長さが $1$ 以上になる）。よって $e$ は閉路に含まれ、橋でない。
(ii) ⇒ (i)：$e$ を含む閉路があったとすると、閉路から $e$ を除いたものは $v$ と $p(v)$ を結ぶ道で、$T_v$ の頂点から始まり外の頂点で終わるので、どこかで $T_v$ の内と外を結ぶ辺を通る。その辺は $e$ でないので (ii) に反する。よって $e$ を含む閉路はなく、$e$ は橋である。
(ii) ⇒ (iii) は明らかで、(iii) ⇒ (ii) は準備による。
(iii) ⇔ (iv)：$x\in T_v$ から出る木に入らない辺 $xw$ の他端 $w$ は、準備と thm-dfs-no-cross により、$T_v$ の頂点（$\mathrm{pre}(w)\ge\mathrm{pre}(v)$）か $v$ の真の先祖（$\mathrm{pre}(w)<\mathrm{pre}(v)$）である。よって $\mathrm{low}(v)<\mathrm{pre}(v)$ であることと、$v$ の真の先祖へ向かうそのような辺があることは同値である。$\square$

全体の手順はすべての頂点を見るので、どの頂点にもいつか印が付き、印が付くのは訪問を始めるときだけで、印は消えないから、各頂点はちょうど 1 回訪問される。頂点 $u$ の訪問で行き先を見る回数は、無向なら $\deg u$、有向なら $u$ から出る辺の本数で、その和はそれぞれ $2m$（握手補題、次数(グラフ) の記事の定理「次数の総和と辺数」）と $m$ である。$\square$

1：$\mathrm{pre}(u)<\mathrm{pre}(v)$ の場合。時刻 $\mathrm{pre}(u)$ に $v$ には印がなく、$u$ の訪問は終わる前に行き先 $v$ を見る。そのとき $v$ に印がなければ $v$ は $u$ の子になり、印があれば $v$ は $u$ の訪問の途中で発見されている。どちらの場合も $\mathrm{pre}(u)<\mathrm{pre}(v)<\mathrm{post}(u)$ で、lem-dfs-parenthesis により $\mathrm{post}(v)<\mathrm{post}(u)$ である。
$\mathrm{pre}(v)<\mathrm{pre}(u)$ の場合。$\mathrm{pre}(u)<\mathrm{post}(v)$ なら、$u$ は $v$ の訪問の途中で発見されたので、lem-dfs-parenthesis の 3 ⇒ 1 により $v$ は $u$ の真の先祖である。そうでなければ $\mathrm{post}(v)<\mathrm{pre}(u)<\mathrm{post}(u)$ である。
2：後退辺 $u\to v$ があれば、木の中の $v$ から $u$ への有向の道（木の辺は親から子へ向かう）に辺 $u\to v$ を加えると有向閉路になる（$v\ne u$ なので $k\ge2$）。逆に後退辺がなければ、1 によりすべての辺 $u\to v$ で $\mathrm{post}(v)<\mathrm{post}(u)$ である。有向閉路 $v_0\to\dots\to v_{k-1}\to v_0$ があれば $\mathrm{post}(v_0)>\mathrm{post}(v_1)>\dots>\mathrm{post}(v_{k-1})>\mathrm{post}(v_0)$ となり矛盾する。
3：有向閉路がなければ 2 により後退辺はなく、1 によりすべての辺 $u\to v$ で $\mathrm{post}(u)>\mathrm{post}(v)$ である。よって終了時刻の大きい順に並べると、どの辺も前から後ろへ向かう。$\square$