Сумма степеней всех вершин графа равна удвоенному количеству рёбер.

Решение:

Это утверждение является Теоремой о рукопожатиях (или леммой о степенях). Она гласит, что сумма степеней всех вершин любого графа равна удвоенному числу его рёбер.

Обоснование: Каждое ребро соединяет две вершины. Когда мы суммируем степени вершин, каждое ребро учитывается дважды (по одному разу для каждой из двух вершин, которые оно соединяет). Таким образом, сумма степеней всех вершин равна удвоенному числу рёбер.

Формула: \( \sum_{v \in V} \deg(v) = 2|E| \), где \( V \) — множество вершин, \( |E| \) — количество рёбер, а \( \deg(v) \) — степень вершины \( v \).

Ответ: Утверждение верно.