Câu hỏi 156
Cho $G$ là một đồ thị đơn giản với các cạnh $n$ và các cạnh $m$. Hai đỉnh được gọi là hàng xóm nếu có một cạnh giữa chúng. Hóa ra $G$ không chứa bất kỳ chu kỳ có độ dài nào từ $3$ đến $2k$ (bao gồm), trong đó $k \ge 2$ là một số nguyên dương nhất định.
a. chứng minh rằng có thể chọn một bộ $S$ không có đỉnh của $G$ sao cho mọi đỉnh trong $S$ có ít nhất $\left\lfloor \frac{m}{n} \right\rfloor$ Hàng xóm trong $S$. ($\lfloor x \rfloor$ là viết tắt của số nguyên nhỏ nhất lớn hơn hoặc bằng $x$.)
b. Giả sử một tập hợp $S$ như được mô tả trong (A) được chọn. Gọi $H$ là đồ thị chỉ bao gồm các đỉnh trong $S$ và các cạnh giữa các đỉnh đó chỉ. Cho $v$ là một đỉnh của $H$. Chứng minh rằng có thể đạt được ít nhất $\left\lfloor \left( \frac{m}{n} - 1 \right)^k \right\rfloor$ của $H$ bằng cách bắt đầu từ $v$ và đi dọc theo các cạnh của $H$ nhiều nhất Các bước $k$. (Lưu ý rằng bản thân $v$ là một đỉnh thỏa mãn điều kiện này, vì nó có thể đạt được bằng cách bắt đầu từ $v$ và đi dọc theo các cạnh của $H$ cho Các bước $0$.)
a. chứng minh rằng có thể chọn một bộ $S$ không có đỉnh của $G$ sao cho mọi đỉnh trong $S$ có ít nhất $\left\lfloor \frac{m}{n} \right\rfloor$ Hàng xóm trong $S$. ($\lfloor x \rfloor$ là viết tắt của số nguyên nhỏ nhất lớn hơn hoặc bằng $x$.)
b. Giả sử một tập hợp $S$ như được mô tả trong (A) được chọn. Gọi $H$ là đồ thị chỉ bao gồm các đỉnh trong $S$ và các cạnh giữa các đỉnh đó chỉ. Cho $v$ là một đỉnh của $H$. Chứng minh rằng có thể đạt được ít nhất $\left\lfloor \left( \frac{m}{n} - 1 \right)^k \right\rfloor$ của $H$ bằng cách bắt đầu từ $v$ và đi dọc theo các cạnh của $H$ nhiều nhất Các bước $k$. (Lưu ý rằng bản thân $v$ là một đỉnh thỏa mãn điều kiện này, vì nó có thể đạt được bằng cách bắt đầu từ $v$ và đi dọc theo các cạnh của $H$ cho Các bước $0$.)