ПРЕДЛОЖЕНИЕ. 2. Если в дереве не менее двух вершин, то у него не менее двух листов.

1. Всякие две вершины дерева можно соединить единственной цепью.

2. Если в дереве не менее двух вершин, то у него не менее двух листов.

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

1. Поскольку дерево является связным графом, то всякие его вершины можно соединить хотя бы одной цепью. Если для каких-нибудь вершин таких путей два (или больше), то в графе есть цикл.

2. Рассмотрим вершины (пусть a, b), цепь между которыми содержит максимальное число дуг. Если какая-нибудь из этих вершин (пусть a) не является листом, то в графе существует дуга (a, c), где вершина c не принадлежит цепи. По первому утверждению вершины b и c соединяются единственной цепью, значит, эта цепь проходит через a и ее длина (число дуг) больше, чем в исходной, что противоречит выбору вершин a и b.

Если изобразить деревья с 1,2,3,4 вершинами, то можно убедиться, что число дуг в них на одну меньше числа вершин. Оказывается, это справедливо для любого дерева. Более того, справедливо и обратное утверждение.

Теорема 17. Для того, чтобы связный неориентированный граф являлся деревом, необходимо и достаточно выполнение равенства q=p- 1.

Доказательство. Необходимость. Доказывать будем по индукции. Если у дерева одна вершина, то дуг нет, и нужное равенство выполняется. Пусть утверждение справедливо для деревьев с числом вершин p >1 и у графа Г число вершин равно p+ 1. По предыдущему предложению у графа Г есть лист (пусть a). Если удалить из дерева эту вершину вместе с инцидентной дугой, то, очевидно, получим дерево с p вершинами, у которого по предположению индукции p- 1 дуга. Таким образом, у графа Г p дуг, что и требовалось.

Достаточность. Пусть связный неориентированный граф не является деревом. Это означает, что в нем есть цикл. В цикле дуг столько же, сколько и вершин. Будем последовательно присоединять остальные вершины графа дугами к уже построенному графу. Поскольку граф связный, это возможно до исчерпания вершин. Таким образом, число использованных дуг равно p, т.е. всего в графе не менее p дуг, противоречие.