is $k_{max}=0$ the correct answer?

Dumel wrote: is $k_{max}=0$ the correct answer? Unfortunately.

Let $G(V,E)$ be the corresponding graph; wlog it is connected. Let $v_0$ be the capital city. Delete $v_0$ and all it's edges. We are left with $m$ disjoint connected components $C_1,...,C_m$. To each component we add a copy of $v_0$, (i.e. $m$ copies of $v_0$ so the components are still disjoint). Note that $\sum_{i=1}^m d_{C_i}(v_0)=2010$ (*) and that we can delete $d_{C_i}(v_0)-1$ edges from $v_0$ for all $i$ and leave the original graph connected. Therefore we can delete $2010-m$ edges in the original graph, so the problem reduces to maximising the number of components. If $d_{C_i}(v_0)$ is odd then $C_i$ has another vertex of odd degree (because $\sum_{v\in V}d(v)=2|E|$ is even). However, if two components have vertices of the same degree then that degree is even. Since all vertices are degree $\le 2009$, it follows that there are at most $\lceil \textstyle\frac{2009}{2}\rceil = 1005$ components with $d_{C_i}(v_0)$ odd. However, from (*) we cannot have an odd number of components with $d_{C_i}(v_0)$ odd, so there are at most $1004$ components with $d_{C_i}(v_0)=1$. Hence, all other components have degree $\ge 2$ so we can delete at least $\textstyle\frac{2010-1004}{2}=503$ edges. To show this is achievable consider the following: Join $1004$ edges from $v_0$ to the disjoint complete graphs $K_3,K_5,...,K_{2009}$. Then join $1006$ edges from $v_0$ to the vertices of $503$ disjoint $K_2$. Hence $k_{\text{max}}=503$.

what about this counter(?)example ? Image not found it seems me that all of the conditions are satisfied, but we can delete the edge between the capital city and 2000. ocha wrote: To show this is achievable consider the following: Join $1004$ edges from $v_0$ to the disjoint complete graphs $K_3,K_5,...,K_{2009}$. Then join $1006$ edges from $v_0$ to the vertices of $503$ disjoint $K_2$. or possibly I misuderstood sth coz the above example looks similar to mine.

You can delete 1997 edges from $v_0$ to the complete bipartite graph and leave it connected...?

ok so you found maximum value of k such that it's always possible to delete k edges leaving graph connected? However I have still understood the problem is to find maximum k such that no matter which k edges we delete, graph remains connected; Quote: there are (...) at least, $2010-1004=1006$ components with even degree $\ge 2$. even for m<1006? //in the above construction I obviously confused 2000 with 2010