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'$ be the graph obtained by removing $v_0$, and let $C$ be a connected component of $G'$. Suppose that there is only one vertex $v'$ in $C$ that is adjacent to $v_0$ in $G$. Either $\deg_G v'$ is odd or, since $C$ must have an even number of odd degree (in $G'$) vertices, $\deg_G v'$ is even and $C$ has another vertex $v''$ with $\deg_G v''$ 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$).