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

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

Доказательство будем проводить методом от противного. Пусть существуют две простые цепи, соединяющие вершину u и v. Тогда вершины u и v входят в простой цикл, что противоречит тому, что - дерево.

u v

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

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

3) Пусть - связный граф и любое ребро есть мост, тогда граф - связный и древовидный.

Древовидность графа будем доказывать методом математической индукции по р.

База индукции: р=1, в этом случае q=0.

Шаг индукции: пусть для всех графов с число вершин меньше р. Рассмотрим граф , . Удалим из этого графа ребро х, которое по условию является мостом. Получим две компоненты связности G’ и G”, удовлетворяющие нашему предположению. Поскольку и в G’ и G” число вершин меньше р. Имеем:

.

4) Пусть - связный и древовидный, покажем, что - ацикличный и древовидный.

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

5) Пусть - ацикличный и древовидный, покажем, что граф связный.

Граф без циклов. Следовательно, его компоненты деревья. Пусть их будет к. Для каждой из компонент будет выполняться условия древовидности. Имеем:

, но , следовательно, к=1.