Рассмотрим две произвольных вершины и предположим, что они не соединены путем, то есть такой последовательностью ребер, в которой начало очередного ребра совпадает с концом предыдущего. Каждая из этих двух вершин по условию соединена не менее, чем с ^n–1/₂ другими; при этом все упомянутые вершины различны – ведь если какие-то две из них совпадают, то есть путь, соединяющий исходные вершины.

  Таким образом, в графе не менее  ^n–1/₂ + ^n–1/₂ + 2 = n + 1  вершин. Противоречие.

Ответ задачи отсутствует