Рассуждения от противного

Рассмотрим дорогу между городами и Докажем, что не более чем за дней она будет разрушена. Предположим, что она не была разрушена за дней. Тогда каждый день разрушалась хотя бы одна дорога, выходящая из города или хотя бы одна дорога, выходящая из города (в противном случае к разрушаемому набору можно было бы добавить дорогу и, значит, он был не идеальным). Таким образом, за дней будут разрушены все дороги, выходящие из городов и кроме дороги Но тогда дорога заведомо попадёт в следующий идеальный набор и будет разрушена на -й день.
Итак, мы про каждую дорогу доказали, что по истечении дней она будет разрушена. Поэтому через дней в стране не останется ни одной дороги.