Cevabımız $503$.
Şeklimizi grafa dönüştürelim.$G$ grafımız genelliği bozmadan bağlantılı olsun. $v_0$ başkent olsun. $v_0$'ı graftan kaldırdığımızı düşündüğümüzde geriye kendi içinde bağlantılı birbiriyle ayrık $C_1,C_{2,\dots ,}C_m$ altgrafları kalsın. $v_0$'dan altgraflara giden yolların toplamı $2010$' dur. Bu yolların sayısını $C_i$ için $d_{C_i}\left(v_0\right)$ ile gösterelim. $$\sum\limits^m_{i=1}{d_{C_i}\left(v_0\right)=2010} \tag {*}$$
Her altgraf için bu yollardan $d_{C_i}\left(v_0\right)-1$ tanesini $G$'nin bağlantılılığı bozulmadan silebiliriz. Çünkü $v_0$'dan altgrafa giden bir kenar bağlantılılığı korumak için yeterlidir. Bu nedenle $G$'den $2010-m$ tane kenar silebiliriz.Dolayısıyla problem altgraf sayısının maksimumunu bulmaya indirgendi.
$d_{C_i}\left(v_0\right)=1$ olacak şekilde kaç altgrafımız olabileceğine bakalım.Eğer $d_{C_i}\left(v_0\right)$ tekse $C_i$ başka tek dereceli bir köşeye daha sahiptir. Çünkü $C_i$ altgrafında köşelerin dereceleri toplamı çifttir. Bununla birlikte eğer $2$ köşe aynı dereceye sahipse bu derece çifttir. Tüm köşelerin dereceleri $\le 2009$ olduğundan en fazla $1005$ tane tek dereceli köşe olabilir. Yani en fazla $1005$ tane altgraf için $d_{C_i}\left(v_0\right)$ tektir.
Ayrıca $\left(*\right)$'dan ötürü $d_{C_i}\left(v_0\right)$ tek olan çift tane $i$ olmak zorundadır. Yani en fazla $1004$ altgraf için $d_{C_i}\left(v_0\right)=1$ olabilir. Kalan her altgraf için $d_{C_i}\left(v_0\right)\ge 2$' dir.O halde $\left(*\right)$'dan ötürü toplam en fazla $1004+\frac{2010-1004}{2}=1507$ altgraf olabilir. Dolayısıyla her durumda $2010-1507=503$ kenar silebiliriz.
Şimdi $503$' ten fazla kenar silemeyeceğimiz bir graf kuralım. $v_0$'a $1004$ kenar ile $K_3,K_5,\dots ,K_{2009}$ bağlayalım. $1006$ kenar ile de $503$ tane $K_2$ bağlayalım. ($K_n$: $n$ köşeli tam graf) $,K_5,\dots ,K_{2009}$'a giden kenarlardan hiçbirini silemeyiz. Kalan $503$ tane $K_2$'nin her birinden en fazla $1$ kenar silebiliriz.
\[k_{max}=503.\]
