В графе нет циклов и вершин на одну больше, чем ребер.

Док-во: 1<=>2: это ясно, т.к. если мы стираем ребро, а связность не нарушается, то значит между его концами есть какой-то другой путь, а значит, есть и цикл. И наоборот: если есть цикл, то можно стереть любое ребро из этого цикла, не нарушив связность графа.

1 =>3: В любом дереве вершин на одну больше; чем ребер. Это мы уже знаем.

3=>4: Пусть цикл все-таки есть. Уберем из него ребро - граф, естественно, останется связным, но это невозможно, т.к теперь ребер на два меньше, чем вершин (см. пред, теорему). Значит, цикла нет.                 4=>1: Пусть граф несвязен. Тогда в каждой компоненте связности нет циклов, то есть каждая компонента - дерево, а значит в ней вершин на одну больше, чем ребер. Но тогда всего вершин более чем на одну больше, чем ребер, что невозможно. Значит, граф связен, а тогда это дерево.

Определение: пусть у нас есть произвольный связный граф. Максимальное дерево в нем - это подграф, который содержит все вершины исходного графа и некоторые из его ребер. Замечание: Таких максимальных деревьев может быть несколько.

Пример: На рисунке выделено одно из возможных максимальных деревьев.

Теорема: В любом связном графе можно выделить максимальное дерево.

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

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

Рассмотрим пример. Для классификации некоторого объекта предприятие. (варианты его названия — ) выберем в качестве корня дерева сам объект. Компоненты, составляющие этот объект, разместим на первом уровне (ярусе) графа: это будут  Второй уровень (ярус) графа содержит компоненты первого уровня (его подмножества: ). Аналогично на третьем уровне разместим подмножества компонентов второго уровня -  От нижнего уровня к высшему ведёт лишь одна дуга, поэтому граф является деревом.

Определение: Минимальным остовным деревом (МОД) связного взвешенного графа называется его связный подграф, состоящий из всех вершин исходного дерева и некоторых его ребер, причем сумма весов ребер максимально возможная. Если исходный граф несвязен, то описываемую ниже процедуру можно применять поочередно к каждой его компоненте связности, получая тем самым минимальные остовные деревья для этих компонент.

Задача о нахождении минимального остовного дерева часто встречается в подобной постановке: есть n городов, через которые можно проложить маршрут так, чтобы можно было добраться из любого города в любой другой (напрямую или через другие города). Требуется найти такой маршрут, чтобы стоимость проезда была максимальной.

Эта задача может быть сформулирована в терминах теории графов как задача о нахождении минимального остовного дерева в графе, вершины которого представляют города, рёбра — это пары городов, между которыми есть маршрут, а вес ребра равен стоимости проезда по соответствующему маршруту.

Существует несколько алгоритмов для нахождения минимального остовного дерева. Некоторые наиболее известные из них перечислены ниже:

·    Алгоритм Прима;

·    Алгоритм Краскала;

·    Алгоритм Борувки.