Question

Задача. Нужно построить граф (как пример) и объяснить

Answer 1

Подойдут все натуральные меньшие 2n. Доказательство проведем по индукции. Пусть существует граф на 2n вершинах для которого найдутся такие k≤2n-1 дорог. Докажем, что и для k+1 это верно.

База: n=2 - просто соединяем последовательно в цепочку вершины.

Переход: пусть для k верно. Выберем две любые вершины, проведем между ними ребро и отметим их. Сделаем то же самое и для неотмеченных вершин. Так как общее количество вершин четное число и на каждом шаге мы отмечаем по две вершины, то мы отметим все вершины по правилам. Итак, у всех вершин степень увеличилась на 1. Переход доказан.