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

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

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

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

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

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

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

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

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

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

4*deg(V) 16n

deg(V) 4n

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

2n + 2 4n

2(n-1) 0

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

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

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