1. Придумайте и нарисуйте два неодинаковых графа, в каждом из которых 6 вершин со степенями 1,1,2,2,3,3. 2. На конференцию собрались ученые. Могло ли оказаться так, что пятеро из них знакомы ровно с тремя другими, а все остальные имеют ровно четверых знакомых среди собравшихся? 3. Придумайте и нарисуйте 3 неодинаковых графа, в каждом из которых по 6 ребер. Найдите сумму степеней всех вершин каждого из этих графов.

1. Чтобы построить граф с заданными степенями вершин $1, 1, 2, 2, 3, 3$, нужно соединить вершины так, чтобы количество выходящих из них ребер соответствовало этим числам. Сумма степеней равна $1+1+2+2+3+3 = 12$, значит в графе $12 / 2 = 6$ ребер. Пример 1: Две группы вершин, образующие два треугольника, в каждом из которых вершины имеют степени $(1, 2, 3)$ — невозможно, так как сумма степеней в компоненте должна быть четной. Правильный пример 1: Цепочка $V1(1)-V2(3)-V3(2)-V4(3)-V5(2)-V6(1)$. Степени: $1, 3, 2, 3, 2, 1$. Правильный пример 2: Цикл из 4 вершин $V1-V2-V3-V4-V1$ (степени по 2) и отдельное ребро $V5-V6$ (степени по 1) не подходит. Возьмем две вершины степени 3 и соединим их между собой и с другими. 2. Используем «Лемму о рукопожатиях»: сумма степеней всех вершин графа всегда четна и равна удвоенному числу ребер. Пусть $n$ — общее число ученых. Пятеро имеют степень 3 (знакомы с 3-мя). Сумма их степеней: $5 \times 3 = 15$. Остальные $(n - 5)$ ученых имеют степень 4. Сумма их степеней: $(n - 5) \times 4$. Общая сумма степеней: $15 + 4(n - 5) = 15 + 4n - 20 = 4n - 5$. Число $4n$ всегда четное, а $4n - 5$ — всегда нечетное. Так как сумма степеней не может быть нечетной, такая ситуация невозможна. **Ответ: Нет, не могло.** 3. Сумма степеней всех вершин графа всегда равна удвоенному количеству его ребер ($2E$). Так как в каждом из 3-х графов по 6 ребер, сумма степеней для любого из них будет: $\sum deg(v) = 2 \times 6 = 12$. **Ответ: 12**.