СРОЧНО! В графе 2n вершин и n^2+1 ребро. Докажите, что для любого n найдётся ребро,...

0 голосов
90 просмотров

СРОЧНО!
В графе 2n вершин и n^2+1 ребро. Докажите, что для любого n найдётся ребро, принадлежащее двум циклам длины 3.


Математика (284 баллов) | 90 просмотров
Дан 1 ответ
0 голосов
Правильный ответ

очевидно при n = 1 не существует графа с 2 ребрами, поэтому n ≥ 2


степень вершины - количество всех ребер, выходящих из вершины deg(v)


сумма степеней всех вершин равна удвоенному количеству всех ребер


т.е. в данном графе сумма степеней вершин


deg(V)=deg(v_1)+deg(v_2)+...+deg(v_{2n})=2n^2+2


будем доказывать от противного. предположим такого ребра нет.


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


поэтому сумма степеней всех вершин среди любых четырех не превосходит 4*2 = 8


рассмотрим четверки:


image

deg(v_2)+deg(v_3)+deg(v_4)+deg(v_5)\leq 8\\

...\\

deg(v_{2n})+deg(v_1)+deg(v_2)+deg(v_3)\leq 8\\ " alt=" deg(v_1)+deg(v_2)+deg(v_3)+deg(v_4)\leq 8\\

deg(v_2)+deg(v_3)+deg(v_4)+deg(v_5)\leq 8\\

...\\

deg(v_{2n})+deg(v_1)+deg(v_2)+deg(v_3)\leq 8\\ " align="absmiddle" class="latex-formula">


сложим все неравенства и получим, что


4*deg(V) ≤ 16n

deg(V) ≤ 4n


но deg(V) по условию равно 2n² + 2


2n² + 2 ≤ 4n

2(n-1)² ≤ 0


неравенство может выполниться только при n = 1, но как уже было отмечено, этот случай не удовлетворяет по условию.


Значит, наше предположение было не верно.


Ответ: доказано.

(271k баллов)