5.12. 全域有向木に関する系

BEST 定理 (および BEST' 定理) を使って有向グラフが持つオイラー回路の個数を数える前に、全域有向木の個数に関する系を一つ証明しておく:

[証明] $\left|V\right|\le 1$ のとき示したい命題は自明なので、一般性を失うことなく $\left|V\right|>1$ と仮定する。もし頂点 $v\in V$ が ${\mathrm{deg}}^{+}v=0$ を満たすなら、$D$ は平衡より ${\mathrm{deg}}^{-}v=0$ が成り立つ。このとき $v$ 以外の任意の頂点から $v$ への路が存在しないので、任意の頂点 $r\in V$ を終根とする全域有向木は $D$ に存在しない。よって一般性を失うことなく任意の頂点 $v\in V$ で ${\mathrm{deg}}^{+}v>0$ だと仮定する。言い換えれば、全ての頂点が $1$ 以上の出次数を持つと仮定する。

$D$ の頂点 $r$, $s$ を任意に取る。$\tau \left(D,r\right)=\tau \left(D,s\right)$ を示せばよい。

$r$ を始点とする弧を任意に取って $a$ とする (${\mathrm{deg}}^{+}r>0$ より $a$ は存在する)。$s$ を始点とする弧を任意に取って $b$ とする (${\mathrm{deg}}^{+}s>0$ より $b$ は存在する)。

BEST' 定理 (定理 5.10.4) を適用すると、次の二つの等式が分かる:

一方、$a$ で始まるオイラー回路の個数は $b$ で始まるオイラー回路の個数と等しい (任意のオイラー回路は任意の弧から始まるように一意に回転できるため)。よって $\epsilon \left(D,a\right)=\epsilon \left(D,b\right)$ が分かる。ここから次の等式が分かる:

両辺を ($0$ でない！) $\prod _{u\in V}\left({\mathrm{deg}}^{+}u-1\right)!$ で割れば $\tau \left(D,r\right)=\tau \left(D,s\right)$ を得る。以上で系 5.12.1 は証明された。□