Задание 6. Можно ли нарисовать граф с 4 вершинами, имеющими степени: 3, 2, 2, 1? Ответ обоснуйте.

Решение:

Задание 6.

Для ответа на этот вопрос воспользуемся теоремой о сумме степеней вершин графа. Теорема гласит, что сумма степеней всех вершин графа равна удвоенному числу его ребер (то есть четному числу).

Даны степени вершин: 3, 2, 2, 1.

Сумма степеней этих вершин:

\[ 3 + 2 + 2 + 1 = 8 \]

Полученная сумма (8) является четным числом. Это означает, что такой граф теоретически может существовать.

Теперь попробуем построить такой граф. Обозначим вершины как \( V_1, V_2, V_3, V_4 \) с соответствующими степенями 3, 2, 2, 1.

1. Начнем с вершины \( V_1 \) со степенью 3. Проведем три ребра от нее: \( V_1 \) к \( V_2 \), \( V_1 \) к \( V_3 \), \( V_1 \) к \( V_4 \).
2. Теперь посмотрим на степени вершин после этих шагов:
• \( V_1 \) уже имеет степень 3 (задание выполнено).
• \( V_2 \) имеет степень 1 (ей нужно еще 1 ребро, чтобы достичь степени 2).
• \( V_3 \) имеет степень 1 (ей нужно еще 1 ребро, чтобы достичь степени 2).
• \( V_4 \) имеет степень 1 (ей нужно еще 0 ребер, чтобы достичь степени 1 — задание выполнено).
3. Нам осталось добавить одно ребро, чтобы степень \( V_2 \) стала 2 и степень \( V_3 \) стала 2. Мы можем соединить \( V_2 \) и \( V_3 \).

В результате мы получим граф со следующими степенями вершин:

• \( V_1 \): соединена с \( V_2, V_3, V_4 \) — степень 3.
• \( V_2 \): соединена с \( V_1, V_3 \) — степень 2.
• \( V_3 \): соединена с \( V_1, V_2 \) — степень 2.
• \( V_4 \): соединена с \( V_1 \) — степень 1.

Таким образом, такой граф нарисовать можно.

Ответ: Да, такой граф нарисовать можно, потому что сумма степеней его вершин (3 + 2 + 2 + 1 = 8) является четным числом, и мы смогли построить пример такого графа.