Изобразите какое-нибудь дерево, в котором: a) 4 вершины степени 3 и 6 вершин степени 1; б) 2 вершины степени 4, 2 вершины степени 3 и 8 вершин степени 1.

Задача выполнима. Для каждой части приведу четкую конструкцию дерева и проверку.

Общие замечания:

• Пусть n — число вершин, сумма степеней равна 2(n−1) для дерева.
• Для части (а): 4 вершины степени 3 и 6 вершин степени 1 ⇒ n = 10, сумма степеней = 4·3 + 6·1 = 18 = 2(n−1) = 18. Г existence ок.
• Для части (б): 2 вершины степени 4, 2 вершины степени 3 и 8 вершин степени 1 ⇒ n = 12, сумма степеней = 2·4 + 2·3 + 8·1 = 22 = 2(n−1) = 22. Г existence ок.

a) Дерево с 4 вершинами степени 3 и 6 вершинами степени 1

Как построить: соединим четыре «внутренние» вершины цепочкой A—B—C—D, к каждому концу и к средним вершинам добавим нужное число листьев, чтобы итоговые степени стали 3.

Названия вершин:

• Внутренние (степени 3): A, B, C, D
• Листья (степени 1): a1, a2, b1, c1, d1, d2

Узлы и рёбра (Edges):

• A — B
• A — a1
• A — a2
• B — b1
• B — C
• C — c1
• C — D
• D — d1
• D — d2

Проверка степеней:

• deg(A) = 3 (с A—B, A—a1, A—a2)
• deg(B) = 3 (B—A, B—C, B—b1)
• deg(C) = 3 (C—B, C—D, C—c1)
• deg(D) = 3 (D—C, D—d1, D—d2)
• Листья a1, a2, b1, c1, d1, d2 имеют deg = 1

Краткая ASCII-«изображение»: a1 | A /
a2 B /
b1 C /
c1 D /
d1 d2

b) Дерево с двумя вершинами степени 4, двумя вершинами степени 3 и восемью вершинами степени 1

Как построить: соединим четыре внутренние вершины цепочкой A—B—C—D так, чтобы концы и середины имели нужные числа листьев.

Названия вершин:

• Внутренние (степени 4 или 3): A (deg 4), B (deg 4), C (deg 3), D (deg 3)
• Листья (степени 1): a1, a2, a3, b1, b2, c1, d1, d2

Узлы и рёбра (Edges):

• A — B
• A — a1
• A — a2
• A — a3
• B — C
• B — b1
• B — b2
• C — D
• C — c1
• D — d1
• D — d2

Проверка степеней:

• deg(A) = 4 (A—B и три листа A—a1, A—a2, A—a3)
• deg(B) = 4 (B—A, B—C, B—b1, B—b2)
• deg(C) = 3 (C—B, C—D, C—a1)
• deg(D) = 3 (D—C, D—d1, D—d2)
• Листья a1, a2, a3, b1, b2, c1, d1, d2 имеют deg = 1

Краткая ASCII-«изображение»: a1 | A / |
a2 a3 B /
b1 b2
C /
c1 D /
d1 d2

Если нужно, можно предоставить альтернативные схемы примерно того же формата (разные ветвления у корня или у внутренних вершин). Также можно реализовать в виде графического рисования на бумаге или в графическом ПО по этим рёбрам.