Показать, что каждое дерево с 2 и более вершинами имеет не менее 2 вершин степени 1. Какие деревья содержат ровно 2 вершины степени 1?

задан 11 Янв 17:59

Рассмотрите дерево как корневое, где корень расположен сверху. Спускаемся вниз по любой ветке. Если дерево конечно (это важно!), то попадаем в висячую (то есть степени 1) вершину.

Если от корня вниз идёт более 1 ветви, то висячих вершин >=2. Если всего одна, то корень является висячей вершиной.

Легко видеть, что ровно 2 висячих вершины у линейного графа.

(11 Янв 19:20) falcao
10|600 символов нужно символов осталось
0

С одной стороны, у дерева В=Р+1.
С другой стороны, просуммировав степени всех вершин, получим удвоенное число рёбер. Если у нас есть не более одной вершины степени 1, то 2Р>=2(В-1)+1=2Р+1. Противоречие.

ссылка

отвечен 11 Янв 19:34

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

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

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

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

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

отмечен:

×4

задан
11 Янв 17:59

показан
107 раз

обновлен
11 Янв 19:34

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

по почте:

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

по RSS:

Ответы

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

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