Cayleyの公式

1. $T$ は連結で 2 頂点以上あるので辺をもつ。$T$ の道（頂点が相異なる歩道）のうち長さ最大のもの $v_0,v_1,\dots,v_k$（$k\geq1$）をとる。$v_0$ に $v_1$ 以外の隣接頂点 $w$ があるとする。$w=v_j$（$j\geq2$）なら $v_0,v_1,\dots,v_j,v_0$ は長さ $j+1\geq3$ の閉路で、$T$ が閉路をもたないことに反する。$w$ が道の上にないなら $w,v_0,\dots,v_k$ はより長い道で、最大性に反する。よって $v_0$ は葉であり、同様に $v_k$ も葉である。$v_0\neq v_k$ なので葉は 2 個以上ある。
2. $T-\ell$ は $T$ の部分グラフなので閉路をもたない。$x,y\in V\setminus\{\ell\}$ を結ぶ $T$ の道 $x=u_0,\dots,u_m=y$ をとる。道の途中の頂点 $u_i$（$0< i< m$）は相異なる 2 頂点 $u_{i-1},u_{i+1}$ に隣接するので次数が $2$ 以上であり、葉 $\ell$ ではない。両端も $\ell$ でないから、この道は $T-\ell$ の道である。よって $T-\ell$ は連結で、木である。
3. $T$ の 2 頂点は $T$ の中で道で結ばれ、$\ell$ と $x\in V$ は $\ell$ から $b$ へ進んでから $T$ の中の道で結ばれるので、$T+\ell b$ は連結である。$T+\ell b$ の閉路が $\ell$ を通るなら、閉路の頂点は閉路の中で 2 つの頂点に隣接するので $\ell$ の次数は $2$ 以上になるが、$\ell$ の次数は $1$ だから、閉路は $\ell$ を通らず $T$ の閉路になって矛盾する。よって $T+\ell b$ は木で、$\ell$ は葉である。$\square$

$n$ に関する帰納法で示す。$n=2$ なら $T$ は 1 本の辺だけで、両頂点の次数は $1$、$P(T)$ は空列なので、どちらの頂点も $0=1-1$ 回現れる。
$n\geq3$ とし、$n-1$ 頂点の木について主張が成り立つとする。最小の葉を $\ell$、その隣を $b$ とすると $P(T)=(b,P(T-\ell))$ である。$T-\ell$ では $b$ の次数が $1$ 減り、$\ell$ 以外の他の頂点の次数は変わらない。帰納法の仮定により、$v\neq\ell$ は $P(T-\ell)$ にちょうど $\deg_{T-\ell}(v)-1$ 回現れる。

• $v=b$ のとき：先頭の 1 回と合わせて $1+(\deg_T(b)-1-1)=\deg_T(b)-1$ 回現れる。
• $v\neq b,\ell$ のとき：先頭には現れないので $\deg_{T-\ell}(v)-1=\deg_T(v)-1$ 回現れる。
• $v=\ell$ のとき：$\ell$ は $T-\ell$ の頂点ではないので $P(T-\ell)$ に現れず、$b\neq\ell$ だから先頭でもない。現れる回数は $0=\deg_T(\ell)-1$ である。
  木は連結で $n\geq2$ なので次数 $0$ の頂点はなく、「現れる回数が $0$」と「次数が $1$」は同値である。$\square$

$n$ に関する帰納法で示す。ここで $V$ は元の個数が $n$ の任意の整数の集合を動く。$n=2$ なら $\mathcal{T}(V)$ は 2 頂点を結ぶ辺 1 本の木だけ、$V^{0}$ は空列だけなので、全単射である。$n\geq3$ とし、元の個数が $n-1$ のすべての整数の集合について主張が成り立つとする。
単射性。$T_1,T_2\in\mathcal{T}(V)$ が $P(T_1)=P(T_2)=(a_1,a_2,\dots,a_{n-2})$ を満たすとする。lem-cayley-formula-degree により $T_1$ と $T_2$ の葉全体はどちらも「$a_1,\dots,a_{n-2}$ に現れない $V$ の元全体」に一致するので、最小の葉は共通の頂点 $\ell$ である。Prüfer 符号の定義から、$\ell$ の隣の頂点は $T_1$ でも $T_2$ でも先頭の $a_1$ であり、$P(T_1-\ell)=P(T_2-\ell)=(a_2,\dots,a_{n-2})$ である。$T_1-\ell$ と $T_2-\ell$ は $V\setminus\{\ell\}$ 上の木なので、帰納法の仮定（単射性）により $T_1-\ell=T_2-\ell$ である。これに同じ辺 $\ell a_1$ を加えると $T_1=T_2$ を得る。
全射性。$a=(a_1,\dots,a_{n-2})\in V^{n-2}$ を任意にとる。$a$ に現れる値は $n-2$ 個以下なので、$a$ に現れない $V$ の元があり、その最小のものを $\ell$ とする。$a'=(a_2,\dots,a_{n-2})$ の成分はどれも $\ell$ ではないので $a'\in(V\setminus\{\ell\})^{n-3}$ であり、帰納法の仮定（全射性）により $P(T')=a'$ となる $V\setminus\{\ell\}$ 上の木 $T'$ がある。$a_1\neq\ell$ だから $a_1\in V\setminus\{\ell\}$ であり、lem-cayley-formula-leaf の 3 により $T:=T'+\ell a_1$ は $V$ 上の木で、$\ell$ はその葉である。
$\ell$ が $T$ の最小の葉であることを示す。$m\neq\ell$ を $T$ の葉とする。$T$ で $a_1$ は $\ell$ と $T'$ の中の頂点の両方に隣接する（$T'$ は 2 頂点以上の連結グラフなので $a_1$ は $T'$ で次数 $1$ 以上）から、次数が $2$ 以上であり、$m\neq a_1$ である。すると $\deg_{T'}(m)=\deg_T(m)=1$ だから $m$ は $T'$ の葉であり、lem-cayley-formula-degree により $m$ は $a'$ に現れない。$m\neq a_1$ とあわせて $m$ は $a$ に現れないので、$\ell$ の最小性により $m>\ell$ である。
よって $T$ の Prüfer 符号を計算する最初の段階では $\ell$ が取り除かれ、その隣の $a_1$ が書き留められ、$T-\ell=T'$ だから $P(T)=(a_1,P(T'))=(a_1,a')=a$ である。以上で全単射性が示された。$\square$

$n=1$ の場合は rem-cayley-formula-plan で確かめた。$n\geq2$ なら、$V=\{1,\dots,n\}$ として thm-cayley-formula-bijection により $|\mathcal{T}(V)|=|V^{n-2}|=n^{n-2}$ である。$\square$

lem-cayley-formula-degree により、木 $T$ の各頂点 $i$ の次数が $d_i$ であることは、$P(T)$ に各 $i$ がちょうど $d_i-1$ 回現れることと同値である。特に、どの木でも $\sum_i(\deg_T(i)-1)$ は $P(T)$ の長さ $n-2$ に等しいので $\sum_i\deg_T(i)=2n-2$ であり、和が $2n-2$ でない組を次数にもつ木はない。和が $2n-2$ のとき、thm-cayley-formula-bijection の全単射により、求める個数は「長さ $n-2$ で、各 $i$ がちょうど $d_i-1$ 回現れる列」の個数に等しい。そのような列は、$n-2$ 個の位置を大きさ $d_1-1,\dots,d_n-1$ の組に分ける方法と 1 対 1 に対応するので、個数は上の多項係数である。$\square$

lem-cayley-formula-degree により、頂点 $1$ が葉であることは $1$ が $P(T)$ に現れないことと同値である。thm-cayley-formula-bijection の全単射により、求める個数は $\{2,\dots,n\}$ の元を成分とする長さ $n-2$ の列の個数 $(n-1)^{n-2}$ に等しい。$\square$

1. $K_n$ はすべての 2 頂点を辺で結ぶので、$\{1,\dots,n\}$ 上のどの木も $K_n$ の全域部分グラフであり、逆に $K_n$ の全域木は $\{1,\dots,n\}$ 上の木である。よって個数は thm-cayley-formula の $n^{n-2}$ に等しい。
2. 各木について根の選び方が $n$ 通りあるので、個数は $n\cdot n^{n-2}=n^{n-1}$ である。$\square$