Безотлагательно!В графе 2n вершин и n^2+1 ребро. Обоснуйте, что для хоть какого

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

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

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

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

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

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

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

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

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

4*deg(V) 16n

deg(V) 4n

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

2n + 2 4n

2(n-1) 0

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

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

Ответ: подтверждено.