Question 108
Given a natural number $n \ge 3$. Find the smallest real number $k \gt 0$ with the following property: If $G$ is a connected graph with $n$ vertices and $m$ edges, then it is always possible to delete no more than $k \cdot \left(m - \left\lfloor \frac{n}{2} \right\rfloor\right)$ edges so that the vertices can be colored in two colors and every undeleted edge has multi-colored vertices.
(Alexander Ivanov)
(Alexander Ivanov)