4. Дано дерево, в котором 4 вершины имеют степень 5, 6 вершин степень 2. Найдите количество вершин степени 1.

Решение:

В любом дереве сумма степеней всех вершин равна удвоенному числу рёбер. Также в дереве число вершин на 1 больше числа рёбер.

Пусть \( n \) — общее число вершин в дереве.

Пусть \( k_i \) — количество вершин степени \( i \).

Пусть \( m \) — число рёбер.

Мы знаем, что \( m = n - 1 \).

Сумма степеней вершин равна \( Σ(deg(v)) = 2m = 2(n-1) \).

По условию задачи:

• 4 вершины имеют степень 5.
• 6 вершин имеют степень 2.
• Пусть \( x \) — количество вершин степени 1 (то, что нам нужно найти).

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

\[ (4 × 5) + (6 × 2) + (x × 1) \]

То есть: \( 20 + 12 + x = 32 + x \).

Также мы знаем, что общее число вершин \( n \) равно сумме вершин всех степеней:

\[ n = 4 + 6 + x = 10 + x \]

Теперь подставим это в формулу удвоенного числа рёбер:

\[ 32 + x = 2(n - 1) \]

\[ 32 + x = 2((10 + x) - 1) \]

\[ 32 + x = 2(9 + x) \]

\[ 32 + x = 18 + 2x \]

\[ 32 - 18 = 2x - x \]

\[ 14 = x \]

Значит, количество вершин степени 1 равно 14.

Ответ: 14