Утверждение: «Любой конечный простой граф, где любая пара вершин имеет хотя бы одного общего соседа, содержит цикл длины не менее 4» является верным.

Доказательство:

Рассмотрим конечный простой граф ( G = (V, E) ), в котором любая пара вершин имеет хотя бы одного общего соседа. Мы будем исследовать, что происходит в таком графе.

Предположение: Возьмем две произвольные вершины ( u ) и ( v ) из ( G ). По условию, существует некая вершина ( w ), такая что обе вершины ( u ) и ( v ) имеют общего соседа ( w ). То есть:

( (u, w) \in E )( (v, w) \in E )

Рассмотрим соседей: Теперь будем продолжать рассматривать остальных соседей. Поскольку граф конечный и простым, мы рассматриваем их степени и количество соседей.

Соседние вершины: Следующим шагом будет анализ соседей ( u ) и ( v ). Если у ( u ) есть еще один сосед, скажем ( x ), который не является ( v ) (и аналогично для ( v )), то оба соседа ( w ) и ( x ) должны быть связаны.

Цикл длины 4: Чтобы доказать, что граф содержит цикл длины 4, давайте рассмотрим следующее:

Если ( u ) и ( v ) имеют хотя бы еще одного общего соседа (например, ( w )), и если ( w ) соединено с некоторой третьей вершиной ( x ), которая является соседом как ( u ), так и ( v ), тогда мы можем образовать цикл. Если существует по меньшей мере один другой общий сосед, то мы можем составить цикл ( u - w - v - x - u ), который будет не менее длиной 4.

Разобьем граф: Если ( G ) может содержать подграф с двумя вершинами, которые имеют одного общего соседа и не могут образовывать другие циклы, возникает конфликт, так как по условию, во всех таких случаях граф начнет предлагать существование циклов.

Контрпример: Для проверки, что граф может не содержать собственные циклы длиной меньше 4, возьмем граф с 3 вершинами ( ( u, v, w ) ):

Все вершины имеют по одному соединению и одного общего соседа. Однако, он содержит только треугольник и не имеет 4-х длины.

Итак, утверждение верно: Любой конечный простой граф, где любая пара вершин имеет хотя бы одного общего соседа, содержит цикл длины не менее 4.