В некотором графе 6 вершин со степенями: 0, 2, 2, 4, 2, 2. Сколько рёбер в этом графе?

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

Формула:

• \[ ∑_{v ∈ V} ext{deg}(v) = 2|E| \]

Где:

• \[ ∑_{v ∈ V} ext{deg}(v) \]
• — это сумма степеней всех вершин.
• \[ |E| \]
• — это количество рёбер.

Решение:

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

   0 + 2 + 2 + 4 + 2 + 2 = 14

2. Применим формулу:

   Сумма степеней = 2 * Количество рёбер

   14 = 2 * Количество рёбер

3. Найдем количество рёбер:

   Количество рёбер = 14 / 2 = 7

Ответ: 7