Рассмотрим связный простой регулярный граф $%G$% , степень любой вершины которого равна четырем. Доказать, что ребра этого графа всегда можно покрасить в два цвета (красный и синий) так, чтобы любая вершина была инцидентна ровно двум синим и ровно двум красным ребрам.

задан 26 Окт '15 2:26

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

Степени всех вершин чётны; граф связен. Значит, в нём имеется эйлеров цикл. Сумма степеней вершин равна удвоенному числу рёбер, и оно оказывается чётным. Тогда рёбра цикла можно поочерёдно раскрасить в красный и синий цвета. Окажется, что в любую вершину мы заходим по ребру одного цвета, а выходим по ребру другого, а потом повторно делаем это ещё раз. В итоге каждая вершина оказывается инцидентна ровно двум синим и ровно двум красным ребрам.

ссылка

отвечен 26 Окт '15 2:49

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

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

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

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

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

отмечен:

×467
×259
×151
×142

задан
26 Окт '15 2:26

показан
1217 раз

обновлен
26 Окт '15 2:49

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

по почте:

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

по RSS:

Ответы

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

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