Cây

Bỏ bất kỳ cạnh nào khỏi một cây cũng làm mất liên thông, và thêm bất kỳ cạnh nào cũng tạo ra một chu trình — một cây có đúng số cạnh cần thiết để nối mọi thứ, không dư không thiếu. Ba điều kiện này mỗi cái chốt lại cấu trúc "vừa đủ" đó từ một góc nhìn khác nhau.

Ta chỉ ra (i) liên thông và không có chu trình $\implies$ (ii) liên thông với $n-1$ cạnh $\implies$ (iii) không có chu trình với $n-1$ cạnh $\implies$ (i), khép kín cả ba điều kiện.

**(i)$\implies$(ii)**, bằng quy nạp theo $n$. Trường hợp cơ sở $n=1$ hiển nhiên: một đỉnh đơn có $0 = n-1$ cạnh. Ở bước quy nạp, xét một đồ thị liên thông không có chu trình $T$ trên $n\ge2$ đỉnh. Vì $T$ hữu hạn và không có chu trình, nó phải chứa một lá $v$ (đỉnh bậc $1$): nếu không, mọi đỉnh sẽ có bậc $\ge 2$, và đi theo các cạnh từ một đỉnh xuất phát bất kỳ mà không quay lại ngay sẽ cuối cùng thăm lại một đỉnh, tạo ra chu trình. Xóa $v$ và cạnh duy nhất kề nó để lại một đồ thị $T'$ trên $n-1$ đỉnh vẫn liên thông ($v$ không có đỉnh nào khác phụ thuộc vào nó để giữ liên thông) và vẫn không có chu trình (đồ thị con của một đồ thị không có chu trình cũng không có chu trình). Theo giả thiết quy nạp, $T'$ có $(n-1)-1$ cạnh, nên $T$ có $(n-1)-1+1 = n-1$ cạnh.

**(ii)$\implies$(iii)**. Giả sử $T$ liên thông với $n-1$ cạnh. Nếu $T$ có một chu trình, xóa một cạnh của chu trình đó sẽ giữ đồ thị liên thông (hai đầu mút của cạnh bị xóa vẫn được nối bởi phần còn lại của chu trình), cho một đồ thị liên thông trên $n$ đỉnh chỉ với $n-2$ cạnh. Nhưng bất kỳ đồ thị liên thông nào trên $n$ đỉnh cũng cần ít nhất $n-1$ cạnh (mỗi đỉnh mới ngoài đỉnh đầu tiên cần ít nhất một cạnh mới để tới được), nên $n-2$ cạnh không thể nối liên thông $n$ đỉnh — mâu thuẫn. Vậy $T$ không có chu trình nào, tức không có chu trình.

**(iii)$\implies$(i)**. Giả sử $T$ không có chu trình với $n-1$ cạnh, và có $c$ thành phần liên thông. Mỗi thành phần tự nó liên thông và không có chu trình, nên theo chiều đã chứng minh (i)$\implies$(ii) áp dụng riêng cho từng thành phần, một thành phần với $n_i$ đỉnh có $n_i - 1$ cạnh. Cộng trên mọi thành phần, tổng số cạnh là $\sum_i (n_i - 1) = n - c$. Vì tổng cho trước là $n-1$, ta có $n - c = n - 1$, nên $c=1$: $T$ liên thông.

Nó trả lời một câu hỏi tổ hợp thuần túy — có bao nhiêu cách khác nhau để nối $n$ điểm phân biệt thành một mạng dạng cây — bằng một công thức đóng đơn giản đến bất ngờ, và thủ thuật mã hóa dùng để chứng minh nó (dãy Prüfer) biến "đếm số cây" thành "đếm số dãy," một bài toán dễ hơn nhiều.

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.