Сколько вершин в графе?

[Alexander Evnin]

В №6 журнала "Математика в школе" за 2014 г. опубликована следующая задача (автор И. Качан из Минска).

Собралось $n$ человек, каждые двое из которых либо знакомы, либо имеют
ровно одного общего знакомого. При этом нет никого, кто был бы знаком со
всеми. Докажите, что $n-1$ --- квадрат целого числа.

Я смог доказать, что граф, возникающий в задаче, регулярный, и если степень каждой вершины равна $k$, то $n=1+k^2$. Примерами таких графов являются $C_5$ и граф Петерсена.
Но есть ли хотя бы ещё один такой граф? Мне удалось доказать, что если $k>2$, то $k=t^2+t+1$ для некоторого натурального $t$. Значит, если есть ещё пример, то в нём минимум 50 вершин.

[Alexander Evnin]

Более аккуратная формулировка задачи в графовых терминах:
сколько вершин может быть в графе, у которого радиус и
диаметр равен 2 и нет циклов длины 3 и 4?

[patzer2097]

Я прошу прощения, такой граф с $50$ вершинами удовлетворяет же Вашему условию?

Alexander Evnin в сообщении #887875 писал(а):

сколько вершин может быть в графе, у которого радиус и диаметр равен 2 и нет циклов длины 3 и 4?

[Alexander Evnin]

Да, удовлетворяет! Спасибо!