У графа три вершины степени 4 и ещё шесть вершин степени 3. Сколько рёбер в этом графе?

Решение:

В теории графов существует лемма о рукопожатиях, которая гласит, что сумма степеней всех вершин графа равна удвоенному числу его рёбер. Это можно записать как:

\[ \sum_{v \in V} \deg(v) = 2|E| \]

Где \( \deg(v) \) — степень вершины \( v \), а \( |E| \) — количество рёбер.

В данном графе:

• Есть 3 вершины степени 4. Суммарная степень этих вершин: \( 3 \times 4 = 12 \).
• Есть 6 вершин степени 3. Суммарная степень этих вершин: \( 6 \times 3 = 18 \).

Общая сумма степеней всех вершин графа равна:

\( 12 + 18 = 30 \)

Согласно лемме о рукопожатиях, эта сумма равна удвоенному числу рёбер:

\( 2|E| = 30 \)

Чтобы найти количество рёбер \( |E| \), разделим сумму степеней на 2:

\( |E| = \frac{30}{2} = 15 \)

Ответ: 15 рёбер.