Докажите, что во всяком простом графе, в котором есть хотя бы две вершины, найдутся две вершины одинаковой степени.

задан 14 Ноя '14 16:54

изменен 14 Ноя '14 21:29

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

Граф простой? Просто для графа с кратными рёбрами это неверно (1-2, 2-3, 2-3: степени 1, 2 и 3 равны соответственно 1, 3 и 2).

(14 Ноя '14 17:09) trongsund

Это верно для простого графа. Воспользуйтесь принципом Дирихле.

(14 Ноя '14 17:10) EdwardTurJ

Да, здесь оговорка насчёт того, что граф простой, обязательна.

Пусть граф имеет n вершин. Посмотрите, какие значения могут принимать их валентности, если их значения не повторяются.

(14 Ноя '14 18:23) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×137

задан
14 Ноя '14 16:54

показан
437 раз

обновлен
14 Ноя '14 18:23

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

по почте:

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

по RSS:

Ответы

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

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