根付き木

段 1（根 $r$ へ戻る写像の性質）． $p$ を根 $r$ へ戻る写像とし、$v\ne r$ からの列を $v=v_0,v_1,\dots,v_k=r$ とする。この列の頂点は相異なる。実際、$i< j\le k$ で $v_i=v_j$ なら $v_i\ne r$ なので $v_{i+1}=v_{j+1}$ などが続き、列は $v_i,\dots,v_{j-1}$ を繰り返して $r$ に達しない。特に $p(v)\ne v$ である。また、相異なる $v,w\ne r$ について $\{v,p(v)\}\ne\{w,p(w)\}$ である。等しければ $w=p(v)$、$v=p(w)$ となり、$v$ からの列が $v,w,v,\dots$ と繰り返すからである。
段 2（$T_p$ は木）． 段 1 より $T_p$ はループのない単純グラフで、辺はちょうど $|V|-1$ 本ある。各頂点 $v$ は列 $v,p(v),\dots,r$ によって $r$ と結ばれるので、$T_p$ は連結である。辺が $|V|-1$ 本の連結グラフは木である（森 の記事の定理「森の同値条件」の 4 で連結成分が 1 個の場合）。
段 3（1 から 2 へ）． 木 $T$ と $v\ne r$ について、$P_v$ から $v$ を除いた部分は $p_T(v)$ と $r$ を結ぶ道なので、道の一意性により $P_{p_T(v)}$ に等しい。よって $\operatorname{dep}(p_T(v))=\operatorname{dep}(v)-1$ であり、親をたどるたびに深さが $1$ ずつ減って、$\operatorname{dep}(v)$ 回で深さ $0$ の頂点 $r$ に達する。したがって $p_T$ は根 $r$ へ戻る。
段 4（互いに逆であること）． $p$ を根 $r$ へ戻る写像とする。段 1 の列 $v,p(v),\dots,r$ は、頂点が相異なり隣どうしが $T_p$ の辺で結ばれるので $T_p$ の道であり、道の一意性によりこれが $T_p$ での $P_v$ である。そのすぐ次の頂点は $p(v)$ なので $p_{T_p}=p$ である。逆に木 $T$ について、$\{v,p_T(v)\}$ は $P_v$ の最初の辺なので $T$ の辺であり、段 3 と段 1 によりこれらは相異なる $|V|-1$ 本である。木 $T$ の辺もちょうど $|V|-1$ 本（木 の記事の命題「木の三つの基本性質」の 3）なので、$T_{p_T}=T$ である。
段 5（2 と 3）． $D_p$ では、$r$ に入る辺はなく、$v\ne r$ に入る辺は $p(v)\to v$ の 1 本だけである。段 1 の列を逆にたどった $r=v_k\to v_{k-1}\to\dots\to v_0=v$ は有向道なので、どの頂点にも $r$ から行ける。逆に 3 の $D$ が与えられたら、$v\ne r$ に入るただ 1 本の辺の始点を $p_D(v)$ とする。$r$ から $v$ への有向道 $r=w_0\to w_1\to\dots\to w_k=v$ をとると、$w_j$ に入る辺は $w_{j-1}\to w_j$ だけなので $p_D(w_j)=w_{j-1}$ であり、$v$ から $p_D$ を $k$ 回たどると $r$ に達する。$p\mapsto D_p$ と $D\mapsto p_D$ が互いに逆であることは定義から直ちに分かる。$\square$

1：thm-rt-three の証明の段 4 により、$P_v$ の頂点は $v,p(v),p^2(v),\dots,r$ である。よって $u\preceq v$ は「ある $k\ge0$ で $u=p^k(v)$」と同値である。$k=0$ から反射律、合成から推移律が従う。$u=p^k(v)$ かつ $v=p^l(u)$ なら、深さは $\operatorname{dep}(u)=\operatorname{dep}(v)-k$、$\operatorname{dep}(v)=\operatorname{dep}(u)-l$ なので $k=l=0$、すなわち $u=v$ であり、反対称律も成り立つ（深さの式は同じ証明の段 3 による）。$r$ はどの $P_v$ の上にもあるので最小元である。$v$ の先祖 $p^i(v)$ と $p^j(v)$（$i\le j$）は $p^j(v)=p^{j-i}(p^i(v))\preceq p^i(v)$ を満たすので比較でき、先祖全体は鎖で、元の個数は $P_v$ の頂点の個数 $\operatorname{dep}(v)+1$ である。$v$ の真の先祖は $p^k(v)$（$k\ge1$）で、どれも $p(v)$ の先祖なので、$p(v)$ が最大元である。
2：$v\ne r$ について、$\{u\mid u< v\}$ は $r$ を含む空でない有限の鎖なので最大元をもつ。それを $p(v)$ とする。$p(v)< v$ なので、$v$ から $p$ をたどる列は $\le$ について真に減少し、$P$ は有限なので止まる。止まるのは $r$ に達したときだけなので、$p$ は根 $r$ へ戻る写像であり、thm-rt-three により根付き木 $(T_p,r)$ が定まる。その親の写像は $p$ である。
$(T_p,r)$ の先祖の順序を $\preceq$ とする。$u\preceq v$ なら $u=p^k(v)$ なので $u\le v$ である。逆に $u\le v$ なら $u\preceq v$ であることを、$v$ の下にある元の個数 $|\{x\mid x< v\}|$ についての帰納法で示す。$u=v$ なら明らかである。$u< v$ なら、$u$ は鎖 $\{x\mid x< v\}$ の元でその最大元が $p(v)$ なので $u\le p(v)$ であり、$p(v)$ の下にある元は $v$ の下にある元より少ないので、帰納法の仮定から $u\preceq p(v)\preceq v$ である。
一意性：先祖の順序が $\le$ に一致する根付き木では、1 により親 $p(v)$ は $\{u\mid u< v\}$ の最大元に限られるので、親の写像は上の $p$ に一致し、thm-rt-three により木も一致する。辺について：$\{v,p(v)\}$ では $p(v)< v$ で、間に元 $x$ があれば $x\le p(v)$ となって矛盾する。逆に $u< v$ で間に元がなければ、$u\le p(v)< v$ から $u=p(v)$ である。よって辺の全体は「間に元のない組」の全体に等しい。$\square$

共通の先祖の全体は $r$ を含み、$v$ の先祖全体という鎖（thm-rt-order の 1）に含まれるので、空でない有限の鎖であり、最大元 $\ell$ をもつ。$u$ から親をたどって $\ell$ に着くまでの道を $Q_u$、$v$ から $\ell$ に着くまでの道を $Q_v$ とすると、長さはそれぞれ $\operatorname{dep}(u)-\operatorname{dep}(\ell)$、$\operatorname{dep}(v)-\operatorname{dep}(\ell)$ である。$Q_u$ と $Q_v$ に共通の頂点 $x$ があれば、$x$ は $u$ と $v$ の共通の先祖で、$\ell$ の子孫である。$\ell$ の最大性から $x=\ell$ である。よって $Q_u$ に $Q_v$ を逆にしてつないだものは $u$ と $v$ を結ぶ道であり、木の道の一意性によりこれが $u$ と $v$ を結ぶただ 1 つの道である。その長さが求める式である。$\square$

1：$v\ne r$ の先祖のうち深さ $1$ のものはちょうど 1 つあり（先祖は深さ $0,1,\dots,\operatorname{dep}(v)$ の頂点を 1 つずつ含む鎖である）、それは $r$ の子である。よって $v$ はちょうど 1 つの $T_{w_i}$ に属する。$T$ の辺は $\{v,p(v)\}$（$v\ne r$）の形である（thm-rt-three）。$v=w_i$ なら $\{w_i,r\}$ であり、そうでなければ $v$ と $p(v)$ はともに $w_i$ の子孫なので $T_{w_i}$ の辺である。
2：$\varphi$ を同型とする。グラフの同型は道を道に写し、$\varphi(r)=r'$ なので、$\varphi(P_v)$ は $T'$ の中で $\varphi(v)$ と $r'$ を結ぶ道、すなわち $P'_{\varphi(v)}$ である。よって $\varphi$ は親・子・先祖・子孫の関係を保ち、$r$ の子を $r'$ の子へ全単射に写し、$T_{w_i}$ を $T'_{\varphi(w_i)}$ へ同型に写す。$\sigma$ として $\varphi$ の制限をとればよい。
逆に $\sigma$ と同型 $\varphi_i\colon(T_{w_i},w_i)\to(T'_{\sigma(w_i)},\sigma(w_i))$ があるとき、$\varphi(r):=r'$、$T_{w_i}$ の上では $\varphi:=\varphi_i$ と定める。1 により $\varphi$ は頂点の全単射である。$T$ の辺は、1 により $\{r,w_i\}$ なら辺 $\{r',\sigma(w_i)\}$ に、$T_{w_i}$ の辺なら $\varphi_i$ により $T'_{\sigma(w_i)}$ の辺に写る。よって $\varphi$ は辺を辺に単射に写し、両方の木の辺の本数はともに頂点数から $1$ を引いたものなので、辺全体の間の全単射を引き起こす。したがって $\varphi$ はグラフの同型で、根を根に写す。$\square$

1：$T_v$ の頂点数についての帰納法による。$\kappa(v)=(\beta)$ で、$\beta$ は既約な列の連結なので釣り合っており、先頭部分の $($ の超過は $0$ 以上である。$\kappa(v)$ の空でも全体でもない先頭部分は「$($ と $\beta$ の先頭部分」なので超過は $1$ 以上であり、全体では $0$ である。
2：先頭部分の超過（$($ の個数から $)$ の個数を引いたもの）が初めて $0$ に戻る位置で切ると、そこまでは既約で、残りは釣り合っている。既約な最初の因子は、超過が初めて $0$ に戻る位置より手前では終われず（終わる位置では超過が $0$）、その位置より先まで続くこともできない（その位置までの先頭部分の超過が $0$ になり、既約性に反する）。よって最初の因子は一意に決まり、残りの長さについての帰納法で全体の一意性が従う。$\square$

頂点数 $|V(T)|$ についての帰納法で示す。$r$ の子を $w_1,\dots,w_k$、$r'$ の子を $w'_1,\dots,w'_l$ とする。各部分木の頂点数は $|V(T)|$ より小さい。
$(T,r)\cong(T',r')$ とする。lem-rt-decompose の 2 により $k=l$ で、全単射 $\sigma$ と同型 $(T_{w_i},w_i)\cong(T'_{\sigma(w_i)},\sigma(w_i))$ がある。帰納法の仮定から $\kappa(w_i)=\kappa'(\sigma(w_i))$ なので、子の括弧列を並べ替えた列は両者で同じであり、$\kappa(r)=\kappa'(r')$ である。
逆に $\kappa(r)=\kappa'(r')$ とする。外側の括弧を除いた列 $\beta_1\cdots\beta_k$ と $\beta'_1\cdots\beta'_l$ は等しい。lem-rt-parse の 1 により $\beta_i,\beta'_j$ は既約なので、同じ補題の 2 により $k=l$ かつ $\beta_i=\beta'_i$ がすべての $i$ について成り立つ。$\beta_i=\kappa(w_{\tau(i)})$、$\beta'_i=\kappa'(w'_{\tau'(i)})$ となる並べ替え $\tau,\tau'$ をとり、$\sigma(w_{\tau(i)}):=w'_{\tau'(i)}$ と定めると、$\sigma$ は子の間の全単射で $\kappa(w)=\kappa'(\sigma(w))$ を満たす。帰納法の仮定から $(T_w,w)\cong(T'_{\sigma(w)},\sigma(w))$ であり、lem-rt-decompose の 2 により $(T,r)\cong(T',r')$ である。$\square$