有向全域木

1⇒2：到達可能性は定義から従う。$(u,r)\in F$ があれば、$r$ から $u$ への有向歩道の後ろに $r$ をつなぐと、$r$ から $r$ への長さ $1$ 以上の有向歩道ができ、長さ $0$ のものと合わせて 2 つになる。よって $\deg^-_F(r)=0$ である。$v\ne r$ への有向歩道は長さ $1$ 以上で、最後の有向辺は $v$ に入るので $\deg^-_F(v)\ge1$ である。$(w,v),(w',v)\in F$（$w\ne w'$）なら、$r$ から $w$、$w'$ への有向歩道の後ろにそれぞれ $v$ をつなぐと、最後から 2 番目の頂点が異なる 2 つの有向歩道ができる。よって $\deg^-_F(v)=1$ である。
2⇒3：有向閉路 $c_0,c_1,\dots,c_\ell=c_0$ があるとする。$r$ は入次数が $0$ なので閉路上にない。閉路上の頂点 $c_i$ に入る $F$ の有向辺はただ 1 本なので、それは閉路の辺 $(c_{i-1},c_i)$ である（添字は $\ell$ を法とする）。$r$ から $c_0$ への有向歩道 $r=x_0,\dots,x_k=c_0$ をとる。$x_j$ が閉路上にあり $j\ge1$ なら、$(x_{j-1},x_j)$ は $x_j$ に入るただ 1 本の有向辺なので、$x_{j-1}$ も閉路上にある。$j=k$ から順に下ると $x_0=r$ が閉路上にあることになり、矛盾する。
3⇒1：$v\ne r$ に対して親 $p(v)$ をとる。頂点の列 $v,p(v),p(p(v)),\dots$ は、根に着くまで定義される。同じ頂点が 2 度現れたとすると、2 度目までの最短の区間を逆にたどったものは有向閉路になり、条件に反する。$V$ は有限なので、ある $k\ge0$ で $p^k(v)=r$ となる（$k$ は最初にそうなる番号）。$r=p^k(v),p^{k-1}(v),\dots,p(v),v$ は $r$ から $v$ への有向歩道である。逆に $r=x_0,\dots,x_m=v$ を任意の有向歩道とすると、$x_m$ に入る有向辺はただ 1 本なので $x_{m-1}=p(x_m)$ であり、順に $x_{m-j}=p^j(v)$ となる。$x_0=r$ で、$r$ には親がないので $m=k$ であり、有向歩道は上のものに一致する。$v=r$ のときも、長さ $1$ 以上の有向歩道は最後の有向辺が $r$ に入るので存在しない。
最後の主張：入次数の和から $\lvert F\rvert=n-1$ である。$T$ は有向閉路をもたないので、ループも、$(u,v)$ と $(v,u)$ の組もない。よって基礎グラフは $n-1$ 本の辺をもち、どの頂点も $r$ と道でつながるので連結である。全域木 の命題「木の判定」により、基礎グラフは木である。$\square$

必要性：有向全域木の有向歩道は $D$ の有向歩道である。
十分性：$v\in V$ について、$r$ から $v$ への有向歩道の長さの最小値を $d(v)$ とする。$v\ne r$ について、長さ $d(v)$ の有向歩道 $r=x_0,\dots,x_k=v$（$k=d(v)\ge1$）を 1 つ選び、$p(v):=x_{k-1}$ とする。$x_0,\dots,x_{k-1}$ は $p(v)$ への長さ $k-1$ の有向歩道なので $d(p(v))< d(v)$ である。$F:=\{(p(v),v)\mid v\ne r\}$ とおくと、$F$ の有向辺の終点は $r$ 以外で、各 $v\ne r$ に入るのは $(p(v),v)$ だけである。$F$ の有向辺に沿って $d$ は真に増えるので、$F$ は有向閉路をもたない。prop-arb-char の 3⇒1 により、$F$ は $r$ を根とする有向全域木である。$\square$

$L[r]$ の行と列は $V':=V\setminus\{r\}$ の元で番号付ける。$x\in V'$ について $\mathbf e_x$ を第 $x$ 成分だけが $1$ の単位ベクトルとし、$\mathbf e_r:=0$ とおく。第 $v$ 列（$v\in V'$）は、$v$ に入るループでない有向辺についての和
$$ L[r]_{\bullet v}=\sum_{u\ne v,\ (u,v)\in A}w(u,v)\,(\mathbf e_v-\mathbf e_u) $$
である（$u=r$ の項では第 $r$ 成分が除かれている）。行列式は各列について線形なので、各 $v\in V'$ に入る有向辺を 1 本ずつ選ぶ選び方、すなわち写像 $f\colon V'\to V$ で $f(v)\ne v$、$(f(v),v)\in A$ となるものすべてについて
$$ \det L[r]=\sum_f\Bigl(\prod_{v\in V'}w(f(v),v)\Bigr)\det M_f,\qquad M_f\text{ の第 }v\text{ 列}:=\mathbf e_v-\mathbf e_{f(v)} $$
となる。$F_f:=\{(f(v),v)\mid v\in V'\}$ とおくと、$\deg^-_{F_f}(r)=0$、$v\in V'$ で $\deg^-_{F_f}(v)=1$ であり、$f\mapsto F_f$ は、ループを含まずこの入次数の条件を満たす $F\subset A$ 全体との全単射である（有向全域木はループを含まないので、どれもこの形をしている）。次を示せばよい。

• $F_f$ が有向閉路をもてば $\det M_f=0$。
• $F_f$ が有向閉路をもたなければ $\det M_f=1$。
  実際そうなら、prop-arb-char の 1⇔3 により、和に残るのはちょうど $F_f$ が有向全域木となる $f$ であり、主張を得る。
  有向閉路 $c_0,c_1,\dots,c_\ell=c_0$ があるとき、$r$ は入次数が $0$ なので閉路上になく、閉路上の各 $c_i$ に入る $F_f$ の有向辺は $(c_{i-1},c_i)$ なので $f(c_i)=c_{i-1}$ である。$f$ は閉路の頂点の集合 $C$ をそれ自身へ全単射に写すから
  $$ \sum_{c\in C}M_{f,\bullet c}=\sum_{c\in C}\mathbf e_c-\sum_{c\in C}\mathbf e_{f(c)}=0 $$
  となり、$M_f$ の列は一次従属で $\det M_f=0$ である。
  有向閉路がないとき、$F_f$ は有向木で、$f(v)$ は $v$ の親である。$v$ への有向歩道の長さを $v$ の深さとすると、親の深さは $v$ の深さより $1$ 小さい。$V'$ の元を深さが小さい順に $v_1,\dots,v_{n-1}$ と並べる。行と列を同じ順に並べ替えても行列式は変わらない。第 $v_j$ 列 $\mathbf e_{v_j}-\mathbf e_{f(v_j)}$ の $0$ でない成分は、対角の $1$ と、$f(v_j)\ne r$ のときの $f(v_j)=v_i$（$i< j$）の行の $-1$ だけである。よって並べ替えた $M_f$ は対角成分が $1$ の上三角行列で、$\det M_f=1$ である。$\square$

$F$ の基礎グラフは prop-arb-char により木で、辺は $G$ の辺なので、$G$ の全域木である。
全単射であること：$G$ の全域木 $T$ を 1 つとる。$T$ は連結なので、$\vec T$ では $r$ からすべての頂点に到達でき、thm-arb-exist により $\vec T$ には $r$ を根とする有向全域木がある。その基礎グラフは $T$ の部分グラフで辺が $n-1$ 本なので $T$ に等しい。逆に、基礎グラフが $T$ になる有向全域木 $F$ は $\vec T$ に含まれる。$F$ の中の $r$ から $v$ へのただ 1 つの有向歩道は、prf-arb-char の 3⇒1 で見た形 $r=p^k(v),\dots,p(v),v$ で頂点が相異なり、$T$ の中の $r$ と $v$ を結ぶ道である。木の中で 2 頂点を結ぶ道はただ 1 つ（森 の定理「森の同値条件」の 3）なので、$v$ の親はその道で $v$ の直前の頂点として $T$ だけから決まる。よって基礎グラフが $T$ の有向全域木はちょうど 1 つである。
すべての重みを $1$ とすると、$L^{\mathrm{in}}(\vec G)$ の対角成分は $G$ の次数、$(u,v)$ 成分は $uv\in E$ のとき $-1$ なので $L^{\mathrm{in}}(\vec G)=L(G)$ である。thm-arb-matrix-tree から最後の等式が従う。$\square$