6–7. В стране из каждого города выходит 100 дорог и от любого города можно добраться до любого другого. Одну дорогу закрыли на ремонт. Доказать, что и теперь от любого города можно добраться до любого другого.

Представим города вершинами, дороги — рёбрами связного графа. Предположим, что закрытие одной дороги разделило граф на две компоненты. Тогда эта дорога была мостом. После её удаления в каждой из двух компонент сумма степеней вершин исходного графа нечётна: сумма степеней внутри компоненты даёт чётное число, а у концов удалённого ребра в исходном графе остаётся по одному дополнительному учёту этой дороги; следовательно, сумма исходных степеней в каждой стороне была нечётной.

Но в исходном графе степень каждого города равна 100, поэтому сумма степеней в любой группе городов равна 100 умножить на число городов и чётна. Противоречие.

Ответ: закрытие одной дороги не нарушает связность; между любыми двумя городами по-прежнему существует маршрут.