Задание 6. Можно ли нарисовать граф с 4 вершинами, имеющими степени: 3, 2, 1? Ответ обоснуйте.

Решение:

Согласно лемме о рукопожатиях (теореме о сумме степеней вершин), сумма степеней всех вершин графа всегда равна удвоенному числу его рёбер, то есть является чётным числом.

В данном случае, сумма степеней вершин равна \( 3 + 2 + 1 + 1 = 7 \). Это нечётное число.

Поскольку сумма степеней вершин должна быть чётной, граф с указанными степенями вершин (3, 2, 1, 1) не может существовать.

Ответ: Нет, нельзя. Сумма степеней вершин графа (3 + 2 + 1 + 1 = 7) является нечётным числом, что противоречит лемме о рукопожатиях.