Câu hỏi 95
Cho đồ thị vô hướng hữu hạn $G$, số nguyên dương $n,d$, mọi đỉnh có bậc không quá $d$, và đỉnh cố định $x$. Gọi $a(n,x)$ là số đồ thị con cảm sinh liên thông gồm $n$ đỉnh có chứa $x$. Đồ thị con cảm sinh có tập đỉnh lấy từ $G$ và giữ đúng mọi cạnh của $G$ giữa các đỉnh đã chọn.
1. Chứng minh $a(n,x)\le2^{nd}$.
2. Chứng minh $a(n,x)\le((d+1)^{d+1}/d^d)^n$.
1. Chứng minh $a(n,x)\le2^{nd}$.
2. Chứng minh $a(n,x)\le((d+1)^{d+1}/d^d)^n$.