ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 30428
Тема:    [ Связность и разложение на связные компоненты ]
Сложность: 3
Классы: 7,8
В корзину
Прислать комментарий

Условие

Докажите, что граф с n вершинами, степень каждой из которых не менее n–1/2, связен.


Решение

  Рассмотрим две произвольных вершины и предположим, что они не соединены путем, то есть такой последовательностью ребер, в которой начало очередного ребра совпадает с концом предыдущего. Каждая из этих двух вершин по условию соединена не менее, чем с n–1/2 другими; при этом все упомянутые вершины различны – ведь если какие-то две из них совпадают, то есть путь, соединяющий исходные вершины.
  Таким образом, в графе не менее  n–1/2 + n–1/2 + 2 = n + 1  вершин. Противоречие.

Источники и прецеденты использования

книга
Автор Генкин С.А., Итенберг И.В., Фомин Д.В.
Год издания 1994
Название Ленинградские математические кружки
Издательство Киров: "АСА"
Издание 1
глава
Номер 6
Название Графы-1
Тема Теория графов
задача
Номер 015

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .