Деревья и остовные деревья

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

Теперь рассмотрим граф без рёбер, попавших в остовное дерево. В полученном графе вершина и ребро (все рёбра вершины в остовном дереве, поэтому её можно не учитывать). Разберём случаи.

Полученный граф связен. В этом случае в нём есть цикл, притом если его удалить, исходный граф останется связным, поскольку мы выделили остовное дерево.

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

В качестве примера на вершинах c ребрами, в котором две вершины и соединены со всеми (в том числе и друг с другом), а остальные вершины соединены только с и