Дано: Связный граф с числом рёбер на единицу меньше числа вершин.
Найти: Доказать, что такой граф является деревом.
Решение:
1. Граф называется деревом, если он связный (т.е. между любой парой вершин существует путь) и не содержит циклов.
2. Пусть у нас есть связный граф с n вершинами и n-1 ребром.
3. Такой граф будет связным, так как между любой парой вершин существует путь.
4. Докажем отсутствие циклов: предположим, что в графе есть цикл.
5. Удалением одного ребра из цикла мы разобьем граф на две компоненты связности, что противоречит его связности.
6. Следовательно, связный граф, у которого число рёбер на единицу меньше числа вершин, является деревом.
Ответ:
Связный граф, у которого число рёбер на единицу меньше числа вершин, является деревом, так как он связный и не содержит циклов.