|
Докажите, что во всяком простом графе, в котором есть хотя бы две вершины, найдутся две вершины одинаковой степени. задан 14 Ноя '14 16:54 
Leva319 |
Здравствуйте
Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Присоединяйтесь!
отмечен:
задан
14 Ноя '14 16:54
показан
1180 раз
обновлен
14 Ноя '14 18:23
Связанные вопросы
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Граф простой? Просто для графа с кратными рёбрами это неверно (1-2, 2-3, 2-3: степени 1, 2 и 3 равны соответственно 1, 3 и 2).
Это верно для простого графа. Воспользуйтесь принципом Дирихле.
Да, здесь оговорка насчёт того, что граф простой, обязательна.
Пусть граф имеет n вершин. Посмотрите, какие значения могут принимать их валентности, если их значения не повторяются.