Найди, сколько рёбер в графе, суммарная степень вершин которого равна 48.

Задача по теореме рукопожатий (Handshake Lemma).

1. Теорема: для любого неориентированного графа сумма степеней всех вершин равна удвоенному числу рёбер ∑ deg(v) = 2|E|.

2. Данo: ∑ deg(v) = 48. Значит 48 = 2|E| → |E| = 24.

3. Примечание и пример: число рёбер не зависит от числа вершин в явном виде, главное чтобы сумма степеней была 48. Например, можно создать граф на 12 вершинах, каждый вершину имеет степень 4 (4-регулярный граф). Тогда число рёбер будет |E| = n·k/2 = 12·4/2 = 24.

Ответ: 24 рёбра.