4. В дереве 8 вершин степени 3, 5 вершин степени 4 и 6 вершин степени 2. Остальные вершины — листья. Сколько всего листьев в этом дереве?

Решение:

Для решения этой задачи воспользуемся теоремой о сумме степеней вершин графа. В любом неориентированном графе сумма степеней всех его вершин равна удвоенному числу его ребер.

\( ∑_{v ∈ V} deg(v) = 2|E| \)

Также, в дереве число ребер на единицу меньше числа вершин: \( |E| = |V| - 1 \).

Следовательно, \( ∑_{v ∈ V} deg(v) = 2(|V| - 1) \).

В данной задаче нам даны:

• 8 вершин степени 3
• 5 вершин степени 4
• 6 вершин степени 2
• Остальные вершины — листья (степени 1). Обозначим количество листьев как \( L \).

Общее число вершин \( |V| \) равно сумме вершин всех степеней:

\( |V| = 8 + 5 + 6 + L \)

Сумма степеней всех вершин:

\( ∑ deg(v) = (8 × 3) + (5 × 4) + (6 × 2) + (L × 1) \)

\( ∑ deg(v) = 24 + 20 + 12 + L = 56 + L \)

Теперь подставим это в формулу \( ∑ deg(v) = 2(|V| - 1) \):

\( 56 + L = 2((8 + 5 + 6 + L) - 1) \)

\( 56 + L = 2(19 + L - 1) \)

\( 56 + L = 2(18 + L) \)

\( 56 + L = 36 + 2L \)

Перенесем \( L \) в правую часть, а числа — в левую:

\( 56 - 36 = 2L - L \)

\( 20 = L \)

Таким образом, количество листьев равно 20.

Ответ: 20