Доказательство. Необходимость. Граф является деревом.

Необходимость. Граф является деревом.

1)От противного: найдутся 2 вершины, соединенные 2-мя цепями: одна цепь. Тогда существует цикл – противоречие.

2)По индукции: для и справедливо.

Предположим, что формула справедлива для дерева с вершинами.

При удалении любого ребра, получим 2 компоненты связности.

вершин в одной компоненте связности, вершин в другой.

Число ребер в первой компоненте связности: .

Число ребер во второй компоненте связности: .

Тогда число ребер в исходном дереве:

, где крайняя единица в начале равенства – удаленное ребро.

3)Доказано через 2-е.

Достаточность.

1)Любые 2 вершины соединены единственной цепью, значит граф связный.

От противного: 2 вершины, соединены 2-мя цепями, существует цикл – противоречие.

2)Граф связный и число вершин n=m+1.

От противного: предположим, что в есть циклы, удалим все висячие вершины (со степенью 1)

, удалим все висячие вершины: получим граф

(! – штрих) степень каждой вершины .

По лемме о рукопожатии:

– противоречие, так как .

3) не содержит циклов, . Надо доказать, что – дерево.

От противного: - не связный граф. Пусть он состоит из компонентов связности, тогда граф:

, где , , …, .

Каждая компонента связности представляет связный граф без циклов, тогда – это деревья. Посчитаем число вершин в этих деревьях. Если граф – дерево, то .

, , …, .

– противоречие, так как , значит – дерево.

Покажем, что в каждом дереве, содержащем более чем 1 вершину, имеется хотя-бы 2 висячие вершины.

От противного:

Возможны 2 случая:

1)Нет висячих вершин.

2)Одна висячая вершина.

В дереве .

По лемме о рукопожатии, сумма степеней вершин:

Рассмотрим 1-й случай:

- противоречие.

Рассмотрим 2-й случай:

- противоречие.