Докажите, что в дереве есть вершина, из которой выходит ровно одно ребро (такая вершина называется висячей).

225

308

Посмотреть ответы 2

Ответы на вопрос:

Умники121212

Другие предметы

4,8(47 оценок)

Рассмотрим произвольную вершину дерева и пойдем по любому выходящему из нее ребру в другую вершину. Если из новой вершины больше ребер не выходит, то мы остаёмся в ней, а в противном случае идём по любому другому ребру дальше. В этом путешествии мы никогда не сможем попасть в вершину, в которой уже побывали: это означало бы наличие цикла. Так как у графа конечное число вершин, то наше путешествие когда-нибудь закончится. Но закончиться оно может только в висячей вершине