4. Постройте дерево, в котором 7 вершин, причём 4 вершины имеют степень 1, 1 вершина степени 2, 2 вершины степени 3.

Такое дерево построить нельзя. В любом дереве с 7 вершинами сумма степеней вершин равна удвоенному числу рёбер, то есть \(2(7-1)=12\). Но указанные степени дают сумму \(4\cdot1+1\cdot2+2\cdot3=12\), что само по себе допустимо; однако вершины степени 3 требуют суммарно шесть инцидентных рёбер, а при перечисленном распределении можно построить дерево.

Например, возьмём вершины A, B, C, D, E, F, G и рёбра AB, AC, AD, BE, BF, CG. Тогда степени A, B, C равны 3, степень E — 1, а степени D, F, G — 1; это даёт три вершины степени 3 и четыре степени 1, поэтому не подходит. Нужное распределение строится рёбрами AB, AC, AD, BE, BF, CG: при этом B и C имеют степень 3 только если добавить ещё ребро, что нарушит число рёбер. Следовательно, условие невозможно реализовать.

Ответ: такое дерево построить нельзя.