В графе любые 2 вершины имеют ровно 2 общих соседа. Докажите, что в этом графе не может быть ровно 100 ребер.

Предыдущий
вопрос Следующий
вопрос

Предположим, что в графе есть ровно 100 ребер. Посчитаем количество пар вершин, которые имеют ровно 2 общих соседа.

Пусть у вершины v_i степень k_i, тогда количество пар вершин, которые имеют общего соседа v_i, равно k_i(k_i-1)/2, так как в графе любая пара общих соседей добавляет одну такую пару. Общее количество пар вершин, имеющих общего соседа, равно сумме k_i(k_i-1)/2 по всем вершинам.

Так как в графе ровно 100 ребер, сумма степеней всех вершин равна удвоенному количеству ребер, то есть 2*100 = 200. Следовательно, сумма k_i^2 по всем вершинам равна 200.

По неравенству Коши-Буняковского получаем:

(Sum(k_i))^2 <= (Sum(1))(Sum(k_i^2)) = 200100 = 20000.

Сумма k_i^2 больше 20000, следовательно, сумма k_i равна 200 и существует вершина с k_i > 1, что противоречит условию задачи.

Таким образом, в графе, где каждые 2 вершины имеют ровно 2 общих соседа, не может быть ровно 100 ребер.