Утверждение. Любой связный граф с $n$ вершинами и $n-1$ рёбрами — дерево (то есть связный ацикличный граф).
Доказательство (коротко). В связном графе существует остовное дерево (спаннинг‑три): алгоритм обхода в глубину/ширину выбирает для каждой новой достижимой вершины одно «деревянное» ребро, образуя подграф без циклов, покрывающий все вершины. Остовное дерево на $n$ вершинах имеет ровно $n-1$ рёбер. Если исходный связный граф тоже имеет $n-1$ рёбер, то он не может содержать дополнительных рёбер сверх остовного дерева, значит совпадает с остовом и поэтому ацикличен. Следовательно, связный граф с $n$ вершинами и $n-1$ рёбрами — дерево.
Контрпример при отсутствии связности. Для $n=4$ возьмём треугольник (цикл из трёх вершин, 3 рёбра) плюс изолированную вершину. Это граф с $n=4$ и $3=n-1$ рёбрами, но он не является деревом (он несвязен и содержит цикл).
Применение в файловых системах (кратко):
- Деревом моделируют иерархию каталогов: вершины — каталоги/файлы, рёбра — «родитель—ребёнок». Связность и отсутствие циклов дают единственный путь от корня к любой сущности, что упрощает навигацию, разрешение путей и операции обхода (DFS/BFS).
- Свойство «$n$ вершин ⇔ остов с $n-1$ рёбрами» объясняет, почему добавление жёсткой ссылки (hard link) на каталог обычно запрещено — это создаёт цикл или ломает уникальность пути.
- Символические ссылки (symlink) придают графу свойства ориентированного/обобщённого графа и могут вводить циклы; поэтому утилиты обхода файловой системы должны обнаруживать и избегать бесконечных циклов (детектирование уже посещённых узлов).
- Для проверки целостности (fsck) и резервного копирования удобно опираться на фактическую структуру‑дерево: если количество рёбер и вершин и связи не соответствуют ожиданию (например, имеются лишние ссылки/циклы), это сигнал о ошибке.
- В распределённых/монтируемых файловых системах структура может быть лесом (несколько корней, mount‑points), что потребует дополнительных соглашений об адресации и обходе.
Кратко: требование связности критично — только при связности $n$ вершин и $n-1$ рёбер гарантируют дерево; в файловых системах это обеспечивает однозначность путей и упрощает алгоритмы управления и проверки.