Задание 2. Начерти граф, в котором: а) 5 вершин и 7 рёбер; б) 6 вершин, степени которых равны 1, 1, 2, 3, 3, 4; в) сумма степеней вершин равна 22.

а) 5 вершин и 7 рёбер. Возьмём вершины A, B, C, D, E и рёбра AB, AC, AD, AE, BC, BD, CE.

б) Степени 1, 1, 2, 3, 3, 4. Подойдёт граф с вершинами A, B, C, D, E, F и рёбрами AB, AC, AD, AE, BC, BD, BE. Тогда степени A–4, B–3, C–2, D–2? Проверим по списку: C имеет степень 2, D — 2, E — 2; этот набор не подходит.

Построим верный вариант: рёбра AB, AC, AD, AE, BC, BD, EF, BF. Степени: A–4, B–4, C–2, D–2, E–2, F–2 — также не подходит. Для заданного набора сумма степеней составляет 14, поэтому число рёбер должно быть 7. Пример: рёбра AB, AC, AD, AE, BC, BD, EF. Степени A–4, B–3, C–2, D–2, E–2, F–1, что не совпадает с требуемым набором.

Искомый набор степеней невозможен: в любом графе число вершин нечётной степени должно быть чётным. Здесь нечётные степени — 1, 1, 3, 3, то есть их четыре, поэтому это условие соблюдено; однако пример можно получить рёбрами AB, AC, AD, AE, BC, BD, EF: степени получаются 4, 3, 2, 2, 2, 1. Следовательно, для реализации набора 1, 1, 2, 3, 3, 4 нужно иначе соединить вершины: возьмём рёбра AB, AC, AD, AE, BC, BF, CD. Степени A–4, B–3, C–3, D–2, E–1, F–1.

Рёбра, соответствующие этому рисунку: AB, AC, AD, AE, BC, BF, CD. Степени: A–4, B–3, C–3, D–2, E–1, F–1. Это совпадает с заданным набором 1, 1, 2, 3, 3, 4.

в) Сумма степеней равна 22. По теореме о рукопожатиях сумма степеней равна удвоенному числу рёбер, значит, требуется 11 рёбер. Например, возьмём 6 вершин A–F и все рёбра полного графа, кроме AB, AC, AD, AE.

В графе должно быть ровно 11 рёбер; их можно задать списком: AC, AD, AE, AF, BC, BD, BE, BF, CD, CE, CF.