Олимпиада имени Леонарда Эйлера2013-2014 учебный год, II тур дистанционного этапа

В стране Думуляндии из каждого города выходило ровно 10 дорог, каждая дорога соединяла ровно два города. При этом сеть дорог была связной, то есть из любого города можно было добраться по дорогам до любого другого, возможно, через другие города. Но во время наводнения затопило два города, соединенные дорогой, после чего эта связность нарушилась (так как через затопленные города ездить нельзя). Докажите, что до наводнения можно было закрыть 9 дорог так, чтобы связность сети дорог также нарушилось.

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Решение. В сумме из затопленных городов выходило 18 дорог в другие города (назовем эти дороги затопленными). После наводнения все города распались минимум на две части, и проехать из одной части в другие можно только через затопленные города. Хотя бы в одну из этих частей ведет не более 9 затопленных дорог. Если бы эти дороги закрыли до наводнения, то из этой части также нельзя бы было проехать в остальные города.