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