Нарисуйте графы со степенями вершин: A) 2, 2, 1, 3; Б) 2, 2, 3, 3; В) 0, 2, 2, 2; Г) 1, 1, 2, 2; Д) 3, 3, 3, 3; Е) 2, 2, 2, 3. Для каждого пункта посчитайте суммарную степень вершин и количество рёбер. Как вы думаете, как связаны эти два количества? Почему это верно для любого графа?

Разберем каждый случай и нарисуем графы, соответствующие заданным степеням вершин. Также посчитаем суммарную степень вершин и количество ребер для каждого графа. Важное замечание: Сумма степеней всех вершин графа всегда равна удвоенному числу ребер в графе. Это известная теорема о рукопожатиях (лемма о рукопожатиях). То есть, если (S) - сумма степеней вершин, а (E) - число ребер, то (S = 2E). A) 2, 2, 1, 3: - Сумма степеней вершин: (2 + 2 + 1 + 3 = 8) - Количество ребер: (8 / 2 = 4) - Граф: * Четыре вершины (A, B, C, D). Степень вершины A - 2, B - 2, C - 1, D - 3. * Ребра: AB, AD, BD, CD Б) 2, 2, 3, 3: - Сумма степеней вершин: (2 + 2 + 3 + 3 = 10) - Количество ребер: (10 / 2 = 5) - Граф: * Четыре вершины (A, B, C, D). Степень вершины A - 2, B - 2, C - 3, D - 3. * Ребра: AC, AD, BC, BD, CD В) 0, 2, 2, 2: - Сумма степеней вершин: (0 + 2 + 2 + 2 = 6) - Количество ребер: (6 / 2 = 3) - Граф: * Четыре вершины (A, B, C, D). Степень вершины A - 0, B - 2, C - 2, D - 2. * Ребра: BC, BD, CD. Вершина А изолирована. Г) 1, 1, 2, 2: - Сумма степеней вершин: (1 + 1 + 2 + 2 = 6) - Количество ребер: (6 / 2 = 3) - Граф: * Четыре вершины (A, B, C, D). Степень вершины A - 1, B - 1, C - 2, D - 2. * Ребра: AC, BC, CD. Д) 3, 3, 3, 3: - Сумма степеней вершин: (3 + 3 + 3 + 3 = 12) - Количество ребер: (12 / 2 = 6) - Граф: * Четыре вершины (A, B, C, D). Степень вершины A - 3, B - 3, C - 3, D - 3. Это полный граф (K_4). * Ребра: AB, AC, AD, BC, BD, CD E) 2, 2, 2, 3: - Сумма степеней вершин: (2 + 2 + 2 + 3 = 9) - Здесь возникает противоречие! Сумма степеней должна быть четной, чтобы соответствовать удвоенному числу ребер. Следовательно, граф с такими степенями вершин не существует. Связь между суммой степеней вершин и количеством ребер: Как уже упоминалось, сумма степеней всех вершин графа всегда равна удвоенному числу ребер. Это фундаментальное свойство графов. Почему это верно для любого графа? Каждое ребро соединяет две вершины и, следовательно, вносит вклад в степень каждой из этих двух вершин. Таким образом, каждое ребро учитывается дважды при суммировании степеней всех вершин графа. Поэтому сумма степеней всегда равна удвоенному числу ребер.