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