木の次数列
$ D_i=
頂点
$ i
の次数とする。
$ N
頂点のグラフが木であることは、以下と
同値
すべての
$ i
について、
$ D_i \geq 1
$ \sum D_i=2N-2
必要性は自明。
十分性は、必ず
$ D_i=1
である
$ i
と
$ D_j \neq1
である
$ j
が存在して（すべて
$ 1
や
$ 2
だと
$ \sum D_i=2N-2
を満たさない）、次数
$ 1
の頂点を次数
$ 2
以上の頂点と結ぶと
$ N-1
頂点のグラフの問題となるので数学的帰納法より示せる。