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

задан 22 Ноя '18 17:02

1

Это неверно: если рёбер нет вообще, то условие выполнено, а заключений -- нет.

(22 Ноя '18 17:46) falcao

@falcao, а если добавить условие, что ребра есть?

(22 Ноя '18 17:57) make78
1

@make78: с такой оговоркой будет верно. Рассмотрим вершину максимальной степени k. Рёбра есть => k > 0. Если k=1, то всё доказано. Если k>=2, то степени k вершин, с которыми соединена данная, принимают значения от 1 до k. Совпадений значений нет по условию => число 1 встречается.

(22 Ноя '18 18:15) falcao

@falcao, понял, спасибо!

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

Ваш ответ

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

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

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

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

отмечен:

×491

задан
22 Ноя '18 17:02

показан
117 раз

обновлен
22 Ноя '18 18:22

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

по почте:

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

по RSS:

Ответы

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

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