プリューファー列
n {\displaystyle n} 頂点の木に対するプリューファー列は n − 2 {\displaystyle n-2} の長さの、 1 {\displaystyle 1} から n {\displaystyle n} の整数からなる一意な列である。 逆に、長さ n − 2 {\displaystyle n-2} で 1 {\displaystyle 1} から n {\displaystyle n} の整数からなるすべての列について、対応する木がただ一つ存在する。
この定理は、ただちに「 n {\displaystyle n} 頂点の木と長さ n − 2 {\displaystyle n-2} で 1 {\displaystyle 1} から n {\displaystyle n} の整数からなる列に全単射が存在する」という系を導く。 列としてありうるものは n n − 2 {\displaystyle n^{n-2}} 個存在するので、 n {\displaystyle n} 頂点の木は n n − 2 {\displaystyle n^{n-2}} 通り存在するとするケイリーの公式が示される。