дискретная-математика - Степени вершин в графе

Эта задача уже была, и я даже нашёл ссылку (хотя и не сразу). Но оставлять её здесь не буду, так как мой ответ оттуда был не вполне продуманным.

Вот новое рассуждение. Пусть простой граф из условия имеет n вершин. Рассмотрим произвольную вершину v. Пусть она имеет степень d. Рассмотрим одну из n-1 вершин, отличных от v. Обозначим её w. Для пары v, w существует ровно две вершины, соединённые с v и w. Возьмём пару рёбер, исходящих из v в эти две вершины, и сопоставим их вершине w. Это будет первое соответствие.

Теперь рассмотрим произвольную пару рёбер, которые выходят из v. Таких пар d(d-1)/2. Для концов рассматриваемых рёбер, отличных от v, существует ровно две вершины, с ними соединённые. Одна из них -- это v. Вторую обозначим через w. Получили второе соответствие. Легко видеть, что этой вершине w по первому соответствию сопоставляется исходная пара рёбер.

Это говорит о том, что оба соответствия взаимно однозначны и взаимно обратны. Отсюда d(d-1)/2=n-1. Следовательно, число d=d(v) однозначно выражается через n > 1 (случай n=1 тривиален).

Полный граф K4 является примером графа из условия при n=4, d=3. Я не знаю, есть ли другие примеры. Ясно, что d>=3, а при d=4 будет n=7. В дополнении графа степени всех вершин равны 2. Тогда это цикл длины 7 или циклы длины 4 и 3. Нетрудно проверить, что условие для них не выполнено, то есть такого примера нет. Что касается случаев d>=4, то здесь мне ответ по поводу существования примеров не известен.

Могу добавить, что при d=5 получается n=11, а такого регулярного графа не имеется ввиду нечётности d и n. Поэтому вопрос о существовании нетривиального примера для меня пока открыт. Что будет при d=6, n=16, я уже не могу сказать. Возможно, там получаются какие-то известные "именные" графы.