Công thức Cayley

Cố định tập đỉnh $\{1,\dots,n\}$ và, với $n\ge2$, định nghĩa dãy Prüfer của một cây có nhãn $T$: lặp lại việc tìm lá có nhãn nhỏ nhất, ghi lại nhãn của đỉnh kề duy nhất của nó, rồi xóa lá đó; dừng khi còn lại $2$ đỉnh. Điều này ghi lại $n-2$ nhãn (mỗi lần xóa một nhãn, vì ta bắt đầu với $n$ đỉnh và dừng ở $2$), nên mỗi cây có nhãn tạo ra một dãy trong $\{1,\dots,n\}^{n-2}$.

Có đúng $n^{n-2}$ dãy như vậy, vì mỗi vị trí trong $n-2$ vị trí độc lập nhận bất kỳ nhãn nào trong $n$ nhãn. Còn phải chỉ ra phép mã hóa này là một song ánh, để các cây có nhãn tương ứng đúng một-một với các dãy này.

Sự kiện then chốt là trong dãy Prüfer, nhãn $i$ xuất hiện đúng $\deg(i)-1$ lần: mỗi khi một đỉnh kề của $i$ bị xóa với vai trò lá, nhãn $i$ được ghi một lần, và bản thân $i$ chỉ bị xóa (không đóng góp lần ghi nào) khi tất cả trừ một cạnh kề của nó đã mất. Đặc biệt, các nhãn không bao giờ xuất hiện trong dãy chính là các lá ban đầu. Điều này cho phép ta giải mã: cho một dãy $(a_1,\dots,a_{n-2})$, lặp lại việc lấy nhãn nhỏ nhất chưa được dùng làm một mục còn lại trong dãy hoặc đã được gắn, nối nó bằng một cạnh với mục đầu tiên còn lại trong dãy, loại nhãn đó khỏi các xét tiếp theo và bỏ mục đó khỏi dãy; sau khi cả $n-2$ mục đã dùng hết, nối $2$ nhãn còn sót lại bằng một cạnh cuối cùng.

Quy trình giải mã này đảo ngược chính xác từng bước quá trình mã hóa — ở mỗi giai đoạn nó xác định đúng lá có nhãn nhỏ nhất và đỉnh kề mà bộ mã hóa lẽ ra đã ghi lại, theo quy nạp trên số đỉnh còn lại. Vậy mã hóa và giải mã là nghịch đảo của nhau, cho một song ánh giữa các cây có nhãn trên $n$ đỉnh và các dãy trong $\{1,\dots,n\}^{n-2}$. Vì có $n^{n-2}$ dãy như vậy, có đúng $n^{n-2}$ cây có nhãn trên $n$ đỉnh.