ケイリーの公式
この結果、記号列{a1,a2, ..., an-2}が得られる。この記号列を「プリューファーコード」と呼ぶ。例えば上図のようなラベル付きの木の場合、「n=6」であり、プリューファーコードは 「{4,4,4,5}」である。
逆も見ていこう。まず、辺のないn個の点だけで構成されるグラフを考えよう。このグラフの中で、記号列「{a1,a2, ..., an-2}」の中にはない、最小の点のラベルをb1として、点b1と点a1を辺で結ぶ。次に、記号列からa1を除去し、点b1に×印を付けよう。次に、記号列「{a2, ..., an-2}」の中にはなく、×印もついていない最小の点のラベルをb2として、点b2と点a2を辺で結ぶ。このように、次々と線を結んでいき、点an-2と点bn-2まで結び、最後に×印の付いていない(点b1からbn-2までに含まれなかった)2点を線で結ぶ。こうしてできたグラフを見ると、最初の木と同じものである。
このように見ていくと、任意に設定したプリューファーコードから、必ず最初に出発した木に戻ることができることが分かる。つまり、記号列「{a1,a2, ..., an-2}」の集合と、n個の点で構成されるラベル付きの木の集合が、1対1で対応していることが言える。証明終。