Добрый день. Как доказать, что если в простом графе степень любой вершины не меньше 3, то в этом есть графе есть цикл длины не менее 4? Куда здесь мыслить? От противного или перейти к дополнению? Спасибо за идеи.

задан 26 Фев '21 22:10

От противного сгодится.

(27 Фев '21 14:42) spades

А можете, подсказать, как это развить? Не могу получить противоречие.

(27 Фев '21 15:32) Cat2021
10|600 символов нужно символов осталось
1

Прежде всего, нужно добавить условие конечности графа. В противном случае утверждение перестаёт быть верным. Далее, можно перейти к связной компоненте, и без ограничения общности считать граф связным. В нём можно выбрать максимальное (остовное) поддерево T. У этого дерева (оно конечное и неодноточеченое) имеется висячая вершина v, соединённая в T с w.

В исходном графе v соединена с какими-то ещё двумя вершинами w1, w2, отличными от w. Если расстояние между w и w1 в дереве T не меньше 2, то вместе с ребром v-w1 образуется цикл длиной >=4. Аналогично для вершины w2. Остаётся рассмотреть случай, когда w1 и w2 удалены от w на расстояние 1. Тогда мы имеем цикл v-w1-w-w2-v длиной 4.

Возможны и какие-то другие способы рассуждения.

ссылка

отвечен 27 Фев '21 18:45

10|600 символов нужно символов осталось
1

Здесь работает принцип крайнего. Двигаемся по графу произвольным образом, но не заходя в уже пройденные вершины. Для конечного графа процесс конечен. Пусть A - последняя вершина. Тогда все соседи А уже повстречались ранее. Пусть В - та вершина из них, которая повстречалась раньше всего. Между В и А лежит как минимум две вершины (соседи А, отличные от В), а значит путь от В к А не менее 3. Добавив к этому пути ребро АВ получим цикл длины не менее 4.

ссылка

отвечен 28 Фев '21 1:53

изменен 28 Фев '21 2:15

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,060
×239

задан
26 Фев '21 22:10

показан
234 раза

обновлен
28 Фев '21 2:15

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru