В некотором графе 6 вершин, степени которых равны: а) 2, 2, 3, 3, 4, 4; Сколько всего рёбер в этом графе?

Решение:

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

\( \sum_{i=1}^{n} d(v_i) = 2|E| \)

Где:

• \( n \) — количество вершин в графе.
• \( d(v_i) \) — степень \( i \)-й вершины.
• \( |E| \) — количество рёбер в графе.

В данном случае у нас 6 вершин, и их степени равны 2, 2, 3, 3, 4, 4.

1. Вычислим сумму степеней всех вершин:

\( d(v_1) + d(v_2) + d(v_3) + d(v_4) + d(v_5) + d(v_6) = 2 + 2 + 3 + 3 + 4 + 4 = 18 \)

2. Теперь применим лемму о рукопожатиях, чтобы найти количество рёбер:

\( 2|E| = 18 \)

Разделим сумму степеней на 2:

\( |E| = \frac{18}{2} = 9 \)

Таким образом, в данном графе 9 рёбер.

Ответ: 9