№ 1. Определите, существует ли граф, если его вершины имеют степени: a) 10, 5, 16, 7, 4; б) 12, 18, 17, 13, 16, 19; в) 4, 1, 11, 6, 7, 11, 6, 3, 1, 13; г) 14, 5, 4, 9, 1, 12, 11, 7, 7, 8; д) 4, 3, 10, 18, 0, 5, 1, 8, 5, 5, 13, 12; Пример записи ответа. Граф существует и в нем ... ребер ИЛИ Граф не существует, т.к. в нем ...

Решение:

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

а) 10, 5, 16, 7, 4

Сумма степеней: \( 10 + 5 + 16 + 7 + 4 = 42 \). Число вершин \( n=5 \). Сумма степеней — четное число. По лемме Гаккеля, такой граф может существовать.

б) 12, 18, 17, 13, 16, 19

Сумма степеней: \( 12 + 18 + 17 + 13 + 16 + 19 = 95 \). Число вершин \( n=6 \). Сумма степеней — нечетное число. По лемме Гаккеля, такой граф не существует.

в) 4, 1, 11, 6, 7, 11, 6, 3, 1, 13

Сумма степеней: \( 4 + 1 + 11 + 6 + 7 + 11 + 6 + 3 + 1 + 13 = 63 \). Число вершин \( n=10 \). Сумма степеней — нечетное число. По лемме Гаккеля, такой граф не существует.

г) 14, 5, 4, 9, 1, 12, 11, 7, 7, 8

Сумма степеней: \( 14 + 5 + 4 + 9 + 1 + 12 + 11 + 7 + 7 + 8 = 78 \). Число вершин \( n=10 \). Сумма степеней — четное число. По лемме Гаккеля, такой граф может существовать.

д) 4, 3, 10, 18, 0, 5, 1, 8, 5, 5, 13, 12

Сумма степеней: \( 4 + 3 + 10 + 18 + 0 + 5 + 1 + 8 + 5 + 5 + 13 + 12 = 84 \). Число вершин \( n=12 \). Сумма степеней — четное число. По лемме Гаккеля, такой граф может существовать.

Пример записи ответа:

Граф существует, т.к. сумма степеней равна 42 (четное число), что соответствует 21 ребру.

Граф не существует, т.к. сумма степеней равна 95 (нечетное число).

Ответ:

а) Граф существует.

б) Граф не существует.

в) Граф не существует.

г) Граф существует.

д) Граф существует.