Câu hỏi 51
Cho một đồ thị đơn liên thông $G$ có bậc lớn nhất $d\gt3$. Giả sử
$$
x_d\ge x_{d-1}+2x_{d-2}+\cdots+(d-1)x_1,
$$
trong đó $x_i$ là số đỉnh có bậc $i$. Chứng minh tồn tại một đỉnh bậc $d$ của $G$ sao cho sau khi bỏ đỉnh ấy, đồ thị vẫn liên thông.
$$
x_d\ge x_{d-1}+2x_{d-2}+\cdots+(d-1)x_1,
$$
trong đó $x_i$ là số đỉnh có bậc $i$. Chứng minh tồn tại một đỉnh bậc $d$ của $G$ sao cho sau khi bỏ đỉnh ấy, đồ thị vẫn liên thông.