Задание 9. Изобразите все деревья с 6 вершинами. Объясните, почему других деревьев нет.

С точностью до переименования вершин существует шесть неизоморфных деревьев с 6 вершинами. Ниже каждое задано списком рёбер, что однозначно задаёт его изображение.

1. Звезда: рёбра 12, 13, 14, 15, 16.
2. Путь: рёбра 12, 23, 34, 45, 56.
3. Два узла степени 3, соединённые ребром: рёбра 12, 13, 14, 25, 26.
4. Ветви длин 1, 1 и 3 от одного узла: рёбра 12, 13, 14, 45, 56.
5. Ветви длин 1, 2 и 2 от одного узла: рёбра 12, 13, 34, 15, 56.
6. Путь с дополнительной вершиной, присоединённой к третьей вершине: рёбра 12, 23, 34, 45, 36.

В дереве с 6 вершинами 5 рёбер. Возможные последовательности степеней вершин (с точностью до порядка): (5,1,1,1,1,1), (4,2,1,1,1,1), (3,3,1,1,1,1), (3,2,2,1,1,1), (3,2,2,1,1,1) с иным расположением ветвей, либо (2,2,2,2,1,1). Перебор связных ациклических вариантов этих форм даёт перечисленные шесть деревьев; иных форм дерева на 6 вершинах нет.