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 дуг, противоречие.