4. Существует ли дерево, в котором: а) 8 вершин и 13 рёбер; б) 15 вершин и 14 рёбер?

Решение:

Для того чтобы граф был деревом, он должен быть связным и не содержать циклов. Основное свойство дерева: количество рёбер всегда на единицу меньше количества вершин. То есть, если n — число вершин, то число рёбер m должно быть равно n - 1.

• а) 8 вершин и 13 рёбер: В этом случае n = 8, а m = 13. Проверим условие: n - 1 = 8 - 1 = 7. Так как 13 ≠ 7, такое дерево существовать не может.
• б) 15 вершин и 14 рёбер: В этом случае n = 15, а m = 14. Проверим условие: n - 1 = 15 - 1 = 14. Так как 14 = 14, такое дерево может существовать (при условии, что оно связное и без циклов, что обычно подразумевается под термином 'дерево').

Ответ: а) Нет; б) Да