В некотором графе 5 вершин, степени которых равны: 12; 5; 14; 10; 9. Сколько в этом графе рёбер?

Решение:

• В теории графов существует лемма о рукопожатиях, которая гласит, что сумма степеней всех вершин графа равна удвоенному числу рёбер.
• \[ Σ \text{deg}(v) = 2|E| \]
• Где \text{deg}(v) — степень вершины, а |E| — количество рёбер.
• Суммируем степени вершин:
• \[ 12 + 5 + 14 + 10 + 9 = 50 \]
• Теперь, согласно лемме, эта сумма равна удвоенному числу рёбер:
• \[ 50 = 2|E| \]
• Чтобы найти количество рёбер, делим сумму на 2:
• \[ |E| = \frac{50}{2} = 25 \]

Ответ: 25