3. Построить граф из 6 вершин, в котором 4 вершины с нечётной степенью (без петель).

Задание 3

Чтобы построить граф с 6 вершинами, из которых 4 вершины имеют нечётную степень, а 2 — чётную (так как сумма степеней всех вершин должна быть чётной и равна удвоенному числу рёбер), мы можем использовать следующее построение:

Представим 6 вершин. Пусть вершины 1, 2, 3, 4 будут с нечётной степенью, а вершины 5, 6 — с чётной.

Например, можно сделать так:

1. Соединим вершины 1, 2, 3, 4 друг с другом так, чтобы они имели степень 3 (нечётная). Это можно сделать, построив полный граф \( K_4 \) из этих вершин. В \( K_4 \) каждая вершина имеет степень 3.
2. Вершины 5 и 6 будут иметь степень 0 (чётная), если мы их никак не соединим с другими вершинами и между собой.

В этом случае у нас будет 4 вершины с нечётной степенью (3) и 2 вершины с чётной степенью (0). Всего 6 вершин.

В данном примере вершины 1, 2, 3, 4 имеют степень 3 (нечётная), а вершины 5 и 6 — степень 0 (чётная).

Ответ: Граф построен.