Утверждение. Пусть неориентированный связный граф $G$ имеет $n$ вершин и ровно $n-1$ рёбер. Тогда $G$ — дерево (то есть связный ациклический граф).
Доказательство. Всякое связное неориентированное конечное графы содержит остовное дерево (спanning tree): можно начать с некоторой вершины и пошагово добавлять рёбра, ведущие к новым вершинам; процесс завершится, когда охвачены все $n$ вершин, и полученное подмножество рёбер образует связный ациклический подграф с $n$ вершинами, следовательно, с $n-1$ рёбрами. Обозначим такое остовное дерево через $T$. Тогда $T$ — подграф $G$ с $n-1$ рёбрами.
Поскольку в условии у $G$ тоже ровно $n-1$ рёбер, не может быть строгого включения $T⊊G$ (иначе $G$ имел бы больше рёбер). Значит $T=G$. Следовательно, $G$ ацикличен и потому является деревом.
Комментарий о равносильных свойствах: для конечного неориентированного графа эквивалентны условия «связный и имеет $n-1$ рёбер», «ацикличный и имеет $n-1$ рёбер», «между любыми двумя вершинами существует ровно один простой путь».
Практическое значение.
- Структуры данных: дерево — минимальная по числу рёбер связная структура на $n$ вершинах, поэтому многие структуры (BST, кучи, деревья разбора) используют эту минимальность для эффективного хранения и обхода; алгоритмы обхода (DFS/BFS) строят остовные деревья, а проверки связности/цикличности сводятся к сравнению числа рёбер с $n-1$.
- Сетевое проектирование: правило показывает минимальное число каналов связи для обеспечения связности сети — $n-1$. В реальных сетях часто добавляют дополнительные рёбра для резервирования, но это вводит циклы, которые требуют специальных протоколов (например, Spanning Tree Protocol) для предотвращения петель маршрутизации. Алгоритмы минимального остова (Kruskal, Prim) используют факт, что оптимальная подключающая сеть имеет ровно $n-1$ рёбер.