Задача следующая: доказать, что в графе на $%k$% вершинах, в котором максимальная степень вершины не превышает трёх и $%k$% четно, всегда можно выбрать подграф на $%\frac{k}{2}$% вершинах, в котором никакие три вершины не образуют цикл длины три. Здесь подграф - это часть вершин, взятая вместе с инцидентными рёбрами из исходного графа.

Пробовал по индукции, но выходит много вариантов переходов. Можно ли как-то иначе?

задан 26 Ноя '19 10:52

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

По теореме Брукса, если степень каждой вершины не больше d, вершины графа можно правильно раскрасить в d+1 цвет. Это легко доказывается индукцией по числу вершин.

Теперь, когда вершины графа раскрашены в 4 цвета, не менее половины из них раскрашены либо в цвета 1 и 2, либо в цвета 3 и 4. Такой подграф с >=k/2 вершинами и выберем (при этом k может быть и нечётным). В нём треугольных циклов нет, так как вершины треугольника нельзя правильно раскрасить в 2 цвета.

ссылка

отвечен 26 Ноя '19 11:17

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

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

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

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

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

отмечен:

×513
×10
×6

задан
26 Ноя '19 10:52

показан
36 раз

обновлен
26 Ноя '19 11:17

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

по почте:

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

по RSS:

Ответы

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

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