В связном графе n вершин, n >= 7, и степень всех вершин равна 3. Докажите, что в этом графе есть простой путь длины 6.

задан 15 Окт 12:23

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

Рассмотрим простой путь p максимальной длины k. Выпишем его вершины: v(0), v(1), ... , v(k). Предположим, что k<=5. Из крайних вершин выходят ещё по 2 ребра. Если они идут в вершину вне пути p, то получается удлинение простого пути. В вершины v(1), ... , v(k-1) может входит только одно дополнительное ребро, не считая рёбер самого пути p.

Допустим, что вершины v(0) и v(k) между собой не соединены. Тогда из каждой выходит по 2 ребра в вершины списка v(1), ... , v(k-1). Это значит, что k-1>=4, то есть k=5. Такая ситуация невозможна, так как помимо 6 вершин списка от v(0) до v(k), у нас есть ещё хотя бы одна вершина v. Граф связен, и из v существует путь в любую из вершин вида v(i). Среди таких путей выберем кратчайший. Тогда окажется, что в какую-то из вершин входит лишнее ребро.

Итак, получается, что v(0) и v(k) соединены, то есть у нас возник простой цикл. Ввиду k<=5, не все вершины графа в нём участвуют, то есть ребро, соединяющее некоторую вершины v(i) с вершиной вне цикла, что ведёт к появлению простого пути длиной > k. Противоречие.

ссылка

отвечен 15 Окт 17:09

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

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

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

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

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

отмечен:

×562

задан
15 Окт 12:23

показан
61 раз

обновлен
15 Окт 17:09

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

по почте:

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

по RSS:

Ответы

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

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