Следствие

В любом нетривиальном дереве имеются, по крайней мере, две висячие вершины.

Доказательство

Доказательство будем проводить методом от противного.

Предположим, что в дереве , существует только одна висячая вершина. Тогда

(одна вершина – висячая - имеет степень 1, (р-1) вершина имеют степень 2 и больше). По условию - дерево. Для него должно выполняться условие:

, а, следовательно, . Получаем . Пришли к противоречию.

Остов

Определение

Остовный подграф графа - это подграф, содержащий все вершины графа.

Определение

Остовный подграф, являющийся деревом называется остовом.

Связный граф может иметь много остовов. Несвязный граф не имеет остова. Но мы можем построить остовы для каждой компоненты связности графа.

Пример

Граф остов остов

Цикломатическое число графа