3. Нарисуйте три разных графа, в каждом из которых 5 вершин. Найдите сумму степеней всех вершин каждого из этих графов.

Решение:

По теореме о сумме степеней всех вершин графа, она равна удвоенному числу его ребер: \( \sum_{i=1}^n deg(v_i) = 2|E| \).

Чтобы нарисовать три РАЗНЫХ графа, будем менять количество ребер.

Граф 1:

Нарисуем граф с 5 вершинами и 4 ребрами (например, дерево).

вершины: \( v_1, v_2, v_3, v_4, v_5 \). Ребра: \( (v_1, v_2), (v_1, v_3), (v_2, v_4), (v_2, v_5) \).

Степени вершин: \( deg(v_1)=2, deg(v_2)=3, deg(v_3)=1, deg(v_4)=1, deg(v_5)=1 \).

Сумма степеней: \( 2 + 3 + 1 + 1 + 1 = 8 \).

Проверка: \( 2|E| = 2 \cdot 4 = 8 \).

Граф 2:

Нарисуем граф с 5 вершинами и 6 ребрами (например, полный граф K₅ минус 4 ребра).

вершины: \( v_1, v_2, v_3, v_4, v_5 \). Ребра: \( (v_1, v_2), (v_1, v_3), (v_1, v_4), (v_2, v_3), (v_2, v_4), (v_3, v_5) \).

Степени вершин: \( deg(v_1)=3, deg(v_2)=3, deg(v_3)=3, deg(v_4)=2, deg(v_5)=1 \).

Сумма степеней: \( 3 + 3 + 3 + 2 + 1 = 12 \).

Проверка: \( 2|E| = 2 \cdot 6 = 12 \).

Граф 3:

Нарисуем полный граф K₅ (5 вершин, все возможные ребра).

Число ребер в K₅ равно \( \frac{5 \times 4}{2} = 10 \).

Степени вершин: \( deg(v_i) = 4 \) для всех \( i=1...5 \).

Сумма степеней: \( 4 + 4 + 4 + 4 + 4 = 20 \).

Проверка: \( 2|E| = 2 \cdot 10 = 20 \).

Ответ: Сумма степеней вершин для графа с 4 ребрами равна 8; для графа с 6 ребрами равна 12; для графа с 10 ребрами равна 20.