Описать структуру графа

[marie-la]

Вот такая задача: описать структуру графа $G$, у которого $N(u)\cup N(v)=V(G), u,v\in G, u\neq v$. $N(u)$ здесь означает окружение вершины $u$.
Я понимаю, что диаметр не больше 2, но этого недостаточно, например, у пятиугольника диаметр 2, но условие не выполнено. Помогите, пожалуйста!

PS Ну вот такая характеристика у меня вышла - между любыми 4 вершинами возможен простой цикл. Как-то не очень красиво.

[arseniiv]

А что подразумевается под структурой?

marie-la в сообщении #1507174 писал(а):

Ну вот такая характеристика у меня вышла - между любыми 4 вершинами возможен простой цикл.

Странно. Возьмём граф, где две компоненты связности — звезда вокруг $u$ и звезда вокруг $v$. В таком графе вообще нет простых циклов длины больше 2.

[svv]

А в $N(u)$ входит сама $u$?

[marie-la]

arseniiv
Так в вашем примере если взять две вершины из первой компоненты, то не выйдет в объединении все множество вершин.

-- 01.03.2021, 20:08 --

svv
Да, входит

[mihaild]

marie-la в сообщении #1507191 писал(а):

если взять две вершины из первой компоненты, то не выйдет в объединении все множество вершин

Условие должно выполняться для любой пары вершин, или должна существовать пара вершин, для которой условие выполнено?

[marie-la]

mihaild
Для любой

[arseniiv]

Вот как! Вот потому я все кванторы стараюсь проговаривать заранее.

Тогда интересно. Действительно, граф должен быть связным и так просто уже его не пригвоздишь.

[mihaild]

arseniiv в сообщении #1507197 писал(а):

Действительно, граф должен быть связным.

Кроме случая графа из 1 либо 2 вершин.

Условие эквивалентно тому, что любая вершина смежна со всеми остальными, за исключением, быть может, одной. Если вершины пронумерованы, то дополнение до такого графа задает перестановку порядка 1 или 2.

[marie-la]

mihaild
Да, думаю, это хорошее описание! Спасибо!