TR-MO 2010 Problem 1

Bir ülkede başkente doğrudan karayolu ile bağlı kentlerin sayısı 2010 dur. Başkent dışındaki her kent 2010 dan az sayıda kente doğrudan karayolu ile bağlı olup, aynı sayıda kente doğrudan bağlı olan herhangi iki kent için bu sayı çifttir. Başkenti doğrudan çeşitli kentlere bağlayan yollardan $k$ tanesi kapatılarak bakıma alınacaktır. Bu ülkedeki karayolu ağı nasıl oluşturulmuş olursa olsun, bunun aralarında karayolu ulaşımı mümkün olan herhangi iki kent arasındaki ulaşımın hâlâ mümkün olacağı biçimde yapılmasını olanaklı kılan en büyük $k$ sayını belirleyiniz.