Связность и связные подграфы (клики)

После закрытия одной дороги ровно 2 города А и В имеют степень вершины 99, а остальные - степень вершины 100.

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