18th Turkish Mathematical Olympiad

The answer is $503$. We want the connected components of the graph $G$ representing the cities and the highways to remain the same when we remove $k$ of the edges incident with the vertex $v_0$ representing the capital. Without loss of generality we may assume that $G$ is connected.

Let $G^{\prime }$ be the graph obtained by removing $v_0$, and let $C$ be a connected component of $G^{\prime }$. Suppose that there is only one vertex $v^{\prime }$ in $C$ that is adjacent to $v_0$ in $G$. Either ${\mathrm{deg}}_G{v}^{\prime }$ is odd or, since $C$ must have an even number of odd degree (in $G^{\prime }$) vertices, ${\mathrm{deg}}_G{v}^{\prime }$ is even and $C$ has another vertex $v^{\prime \prime }$ with ${\mathrm{deg}}_G{v}^{\prime \prime }$ odd. In either case $C$ has a vertex of odd degree (in $G$). On the other hand, if $C$ is connected to $v_0$ by at least two edges, then at least one of these can be removed without affecting connectedness. Since odd degrees can take at most $1005$ values and the number of odd degree vertices must be even, there are at most $1004$ odd degree vertices in $G$. Hence at least $(2010-1004)/2=503$ edges incident with $v_0$ can be removed without disconnecting $G$.

Now we construct a graph $G$ in which more than $503$ edges cannot be removed. The vertices of $G$ are $v_i$, ($0\le i\le 2010$), and $w_{ij}$, ($1<i\le 1004$, $1\le j\le 2i-2$), and the edges of $G$ are $\{v_0,v_i\}$, ($1\le i\le 2010$), $\{v_i,w_{ij}\}$, ($1<i\le 1004$, $1\le j\le 2i-2$), $\{v_{2m-1},v_{2m}\}$, ($503\le m\le 1005$), and $\{w_{i,2m-1},w_{i,2m}\}$, ($1<i\le 1004$, $1\le m\le i-1$).