Các đặc trưng tương đương của cây

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.