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

294

308

Посмотреть ответы 2

Ответы на вопрос:

veronicapcheli

Математика

4,6(71 оценок)

очевидно при 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, но как уже было отмечено, этот случай не удовлетворяет по условию.

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

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

maximbond04

Математика

4,4(64 оценок)

25-100% 5-x x=20% 5-20% 3-x x=15 ответ: 0.15

Реши свою проблему, спроси otvet5GPT

Быстро
Мгновенный ответ на твой вопрос
Точно
Бот обладает знаниями во всех сферах
Бесплатно
Задай вопрос и получи ответ бесплатно

Задай свой вопрос

Популярно: Математика

Есть вопросы?

Как otvet5GPT работает?

otvet5GPT использует большую языковую модель вместе с базой данных GPT для обеспечения высококачественных образовательных результатов. otvet5GPT действует как доступный академический ресурс вне класса.
Сколько это стоит?

Проект находиться на стадии тестирования и все услуги бесплатны.
Могу ли я использовать otvet5GPT в школе?

Конечно! Нейросеть может помочь вам делать конспекты лекций, придумывать идеи в классе и многое другое!
В чем отличия от ChatGPT?

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