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

задан 15 Май '15 16:41

изменен 15 Май '15 17:35

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

Здесь в неравенстве, видимо, опечатка: подразумевается $%n\ge3$%.

Для $%n=3$% рассматриваем два соединённых по вершине отрезка. Степени вершин: 1, 1, 2. Этот граф связен. Добавляем 4-ю вершину, соединяя со всеми, кроме первой по списку. Это даёт список степеней вершин 1, 2, 2, 3. Далее добавляем пятую вершину, соединяя с двумя последними вершинами степени 2 и 3. Получаются числа 1, 2, 2, 3, 4. Ясно, что все графы получаются связными. Шестую вершину соединяем с тремя последними, получая список степеней 1, 2, 3, 3, 4, 5. Следующую вершину соединяем с тремя последними, получая 1, 2, 3, 3, 4, 5, 6. И так далее. В списках какие-то два числа повторяются, и новое соединение осуществляется с теми вершинами, которые идут со второго из повторяющихся чисел. Общая закономерность здесь понятна.

ссылка

отвечен 15 Май '15 17:24

@falcao т.е. какого-то общего для n нет доказательства? (возьмем n вершин и т.д.) Я как-то абстрактнее думала, спасибо за идею.

(15 Май '15 17:39) sleepless_study
1

@sleepless_study: общее доказательство есть, просто я не выписывал саму закономерность. Она отсюда легко извлекается. Там при чётном и нечётном n последовательности выглядят чуть по-разному. Если n=2k+1, то к списку чисел от 1 до n-1 добавляем k, и если n=2k, то тоже добавляем k. А потом просто по индукции рассуждаем, разбирая два случая -- это если оформлять подробно.

(15 Май '15 17:50) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×135

задан
15 Май '15 16:41

показан
620 раз

обновлен
15 Май '15 17:50

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

по почте:

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

по RSS:

Ответы

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

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