Cтраница 4
В этом случае имеется лишь одно дерево, и оно имеет одно ребро. Предположим, что лгсбэе дерево с & / г вершинами содержит k - I ребро, и рассмотрим произвольное дерево с п вершинами. Если в конечном графе нет висячих вершин, то в нем обязательно есть замкнутые пути. Удалим из дерева эту вершину и ребро, из нее выходящее. Получим снова связный граф, являющийся деревом. Следовательно, исходное дерево содержит п - 1 ребро. [46]