Подойдут все натуральные меньшие 2n. Доказательство проведем по индукции. Пусть существует граф на 2n вершинах для которого найдутся такие k≤2n-1 дорог. Докажем, что и для k+1 это верно.
База: n=2 - просто соединяем последовательно в цепочку вершины.
Переход: пусть для k верно. Выберем две любые вершины, проведем между ними ребро и отметим их. Сделаем то же самое и для неотмеченных вершин. Так как общее количество вершин четное число и на каждом шаге мы отмечаем по две вершины, то мы отметим все вершины по правилам. Итак, у всех вершин степень увеличилась на 1. Переход доказан.
Answers & Comments
Подойдут все натуральные меньшие 2n. Доказательство проведем по индукции. Пусть существует граф на 2n вершинах для которого найдутся такие k≤2n-1 дорог. Докажем, что и для k+1 это верно.
База: n=2 - просто соединяем последовательно в цепочку вершины.
Переход: пусть для k верно. Выберем две любые вершины, проведем между ними ребро и отметим их. Сделаем то же самое и для неотмеченных вершин. Так как общее количество вершин четное число и на каждом шаге мы отмечаем по две вершины, то мы отметим все вершины по правилам. Итак, у всех вершин степень увеличилась на 1. Переход доказан.