Дано:
а) Количество вершин: 8; Количество рёбер: 13.
б) Количество вершин: 15; Количество рёбер: 14.
Найти:
Существует ли дерево с указанными параметрами.
Решение:
В дереве с n вершинами количество рёбер m всегда равно n - 1. Следовательно, для существования дерева должно выполняться условие m = n - 1.
а) Для 8 вершин:
m должно быть 8 - 1 = 7. Но у нас 13 рёбер, значит, дерево не может существовать.
б) Для 15 вершин:
m должно быть 15 - 1 = 14. У нас 14 рёбер, значит, дерево может существовать.
Ответ: а) Дерево не существует; б) Дерево существует.