Принцип крайнего

Рассмотрим граф, в котором вершины — города, ребра — дороги. Нам нужно покрыть вершины этого графа непересекающимися путями. Выберем покрытие вершин наименьшим количеством путей. Пусть в этом покрытии хотя бы путей. Если концы каких-то двух путей смежны, то эти два пути можно объединить в один путь, уменьшив их количество. Следовательно, если взять по одному концу от каждого пути, образуется независимое множество из не менее чем вершин. Но это множество противоречит условию задачи, следовательно, среди губерний есть циклы. Если есть циклы, то можно повторить прошлое рассуждение, только из циклов можно брать любую вершину. Следовательно, путей не больше Если два конца какого-то из путей не смежны друг с другом, то можно взять в независимое множества оба этих конца, а из оставшихся губерний, если они циклы брать любую вершину, иначе брать любой из концов, и опять получить противоречие. Таким образом, все вершины разбиваются на не пересекающихся циклов. Вспомним, что наш граф связен, поэтому между какими-то двумя циклами должно быть ребро. Теперь легко из этих двух циклов, соединенных ребром, сделать один путь. Таким образом, мы покрыли все вершины путями.