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

В записи есть противоречие: начальное «Нет» и утверждение о том, что граф может существовать, не согласуются. Последний вывод верен: такой простой граф существует. Чётная сумма степеней и чётное число вершин нечётной степени сами по себе не доказывают существование графа, поэтому приведём пример.

Возьмём вершины A, B, C, D, E и рёбра AB, AC, AD, BC, BE, CD. Тогда степени вершин равны: A — 3, B — 3, C — 3, D — 2, E — 1. Петлей и кратных рёбер нет.

Ответ: да, простой граф с такими степенями существует.