Câu hỏi 108
Cho số tự nhiên $n \ge 3$. Tìm số thực nhỏ nhất $k \gt 0$ có tính chất sau: Nếu $G$ là một đồ thị liên thông có $n$ đỉnh và $m$ cạnh thì luôn có thể xóa không quá $k \cdot \left(m - \left\lfloor \frac{n}{2} \right\rfloor\right)$ cạnh sao cho có thể tô các đỉnh bằng hai màu mà mọi cạnh không bị xóa đều có hai đầu mút khác màu.
(Alexander Ivanov)
(Alexander Ivanov)