Công thứcĐã chứng minh

Công thức Cayley cho cây có nhãn

Phát biểu

Với mọi số nguyên $n \ge 1$ , số cây trên $n$ đỉnh có nhãn $\{1,\dots,n\}$ là $n^{n-2}$ (với quy ước $1^{-1}=1$ khi $n=1$ ).

Vì sao đúng?

Mọi cây có nhãn trên $n$ đỉnh đều có thể mã hóa duy nhất thành một dãy gồm $n-2$ nhãn đỉnh (mã Prüfer của nó) bằng cách lặp đi lặp lại việc bứt chiếc lá có nhãn nhỏ nhất và ghi lại đỉnh kề với nó; ngược lại, mọi dãy độ dài $n-2$ từ $\{1,\dots,n\}$ đều giải mã thành một cây duy nhất, nên có tất cả $n^{n-2}$ cây như vậy.

Phác thảo chứng minh

Xây dựng song ánh Prüfer giữa các cây có nhãn trên $\{1,\dots,n\}$ và các dãy trong $\{1,\dots,n\}^{n-2}$ : ở mỗi bước trong $n-2$ bước, xóa chiếc lá có nhãn nhỏ nhất và ghi thêm nhãn của đỉnh kề duy nhất của nó vào dãy, cuối cùng còn lại một cạnh duy nhất. Nhận xét rằng một đỉnh $v$ xuất hiện trong dãy Prüfer đúng $\deg(v)-1$ lần, nên các lá của cây ban đầu chính là những nhãn không xuất hiện trong dãy, giúp mỗi bước đều đảo ngược được một cách duy nhất và thiết lập song ánh.

Chủ đề chứa định lý này

Cây

Định lý liên quan

Bổ đề bắt tay

Chứng minh từng bước

Chưa có chứng minh từng bước cho định lý này.

Tài liệu tham khảo

Arthur Cayley (1889). A theorem on trees