Как доказать, что для всякого n>=3 существует n-вершинный связный граф без петель и кратных ребер, содержащий n-1 вершин с неравными друг другу степенями.

задан 15 Сен '18 23:00

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

Это делается по индукции. Для n=3 можно рассмотреть случай степеней 011 или 112. Эти варианты равноценны. Сосредоточимся на втором, чтобы не было нулей. Добавим 4-ю вершину. Её мы имеем право соединить с любым набором вершин. При этом её степень станет равна числу соединений. От 112 можно перейти к 1232, соединяя новую вершину с вершинами степеней 1 и 2. Упорядочивая, имеем 1223. Пятую вершину можно соединить с 23. Упорядочение даст 12234. Шестую соединяем с последними тремя. Будет 123345. Закономерность легко вырисовывается. Далее пойдут 1233456, 12344567, и так далее. В зависмости от чётности, понятно, что надо на дальнейшем шаге делать.

ссылка

отвечен 16 Сен '18 3:52

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

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

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

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

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

отмечен:

×1,270
×128

задан
15 Сен '18 23:00

показан
111 раз

обновлен
16 Сен '18 3:52

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

по почте:

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

по RSS:

Ответы

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

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