очевидно при n = 1 не существует графа с 2 ребрами, поэтому n ≥ 2
степень вершины - количество всех ребер, выходящих из вершины deg(v)
сумма степеней всех вершин равна удвоенному количеству всех ребер
т.е. в данном графе сумма степеней вершин
будем доказывать от противного. предположим такого ребра нет.
рассмотрим любые 4 вершины, чтобы среди них не было ребра, которое принадлежит двум циклам длины 3, среди них может быть проведено не более 4 ребер, как бы не проводили пятое, всегда оно дополнит второй цикл.
поэтому сумма степеней всех вершин среди любых четырех не превосходит 4*2 = 8
рассмотрим четверки:
сложим все неравенства и получим, что
4*deg(V) ≤ 16n
deg(V) ≤ 4n
но deg(V) по условию равно 2n² + 2
2n² + 2 ≤ 4n
2(n-1)² ≤ 0
неравенство может выполниться только при n = 1, но как уже было отмечено, этот случай не удовлетворяет по условию.
Значит, наше предположение было не верно.
ответ: доказано.
а) Числа 34956 и 72
б) Всего существует два двузначных числа, которые кратны 36: это 36 и 72.
По очереди уберем их из списка и посчитаем количество пятизначных чисел, делящихся на 4. Уберем сначала 36. Остались цифры 2,4,5,7,9. Число делится на 4 тогда, когда последние его две цифры делятся на 4. Выберем из этих цифр пары, которые образуют число кратное 4: 24, 92, 72, 52. Их всего 4. Рассмотрим число abcde, две последние цифры которого зафиксированы. Значит существует 3!=6 различных чисел с теми же цифрами. Мы нашли 4 двузначных числа, для каждого из которых существует 6 пятизначных чисел. Итого, 6*4=24 числа. Теперь уберем число 72 из списка. Оставшиеся цифры: 3,4,5,6,9. Только числа 64, 56 и 96 делится на 4, а еще оказывается и число 36... Вроде больше нет. Значит пятизначных чисел, делящихся на 4 ровно 6×4=24. Всего получили 24+24 = 48. Всего 48 пар чисел.
в) Если двузначное число 36, то максимальное пятизначное число, которое можно составить из оставшихся чисел, равно 97524. Тогда сумма равна 97524+36=97560. Если же двузначное число 72, то максимальное пятизначное число, которое можно составить равно 95364. Сумма этого числа с 72 явно меньше предыдущей полученной суммы. Значит максимальная сумма равна 97560
