Ответ: а) цепь и звезда; б) цепь, звезда и «вилка».
Пояснение
Идея. Деревья неодинаковы, если у них разное строение — например, разный набор степеней вершин. Строим деревья с нужным числом вершин по-разному: цепью, звездой, с развилкой.
1Любое дерево из n вершин имеет n − 1 рёбер (§47*), поэтому у четырёх вершин три ребра, у пяти — четыре. Рисуем, следя, чтобы не было циклов и частей, не соединённых между собой.
2С четырьмя вершинами: все вершины в одну цепочку или три конца, соединённые с одной вершиной (звезда). Других форм нет.
3С пятью вершинами: цепочка из пяти; звезда с четырьмя концами; цепочка, в которой одна из вершин вторым ребром тянет ещё два конца (вилка со степенью 3).
4Если набор степеней вершин у двух деревьев разный, переставлением вершин одно в другое не перейдёт — значит, деревья действительно разные.
