Задание 3: Нарисуйте в тетради какое-нибудь дерево, в котором 7 вершин, причём степень 1 имеют ровно: a) 2 вершины; б) 4 вершины; в) 6 вершин.

Решение: Дерево - это связный граф без циклов. Степень вершины - это количество ребер, инцидентных этой вершине. Вершина степени 1 называется листом. a) Если в дереве 7 вершин, и 2 из них имеют степень 1, то это возможно. Например, можно нарисовать дерево в виде линии (путь) с двумя концевыми вершинами (степени 1) и остальными промежуточными вершинами (степени 2). Или дерево-звезда с центральной вершиной и двумя листьями. б) Если в дереве 7 вершин, и 4 из них имеют степень 1, то это тоже возможно. Можно нарисовать дерево с одной вершиной степени 4, а все остальные вершины будут листами. в) Если в дереве 7 вершин, и 6 из них имеют степень 1, то это невозможно. В дереве сумма степеней всех вершин равна удвоенному числу ребер. В дереве с 7 вершинами имеется 6 ребер. Значит сумма степеней должна быть 12. Если 6 вершин имеют степень 1, то их суммарная степень 6. Тогда оставшаяся вершина должна иметь степень 12 - 6 = 6. Но чтобы соединить 6 листьев, необходимо хотя бы 5 ребер. Это возможно.