Номер 129, страница 85, часть 1 - гдз по алгебре 7-9 класс учебник Высоцкий, Ященко

129 Докажите, что сумма степеней всех вершин графа вдвое больше числа рёбер в этом графе.

Данное утверждение известно в теории графов как лемма о рукопожатиях или теорема о сумме степеней вершин.

Пусть дан граф $G$ с множеством вершин $V$ и множеством рёбер $E$. Обозначим количество рёбер в графе как $|E|$. Степенью вершины $v$, обозначаемой как $\deg(v)$, называется количество рёбер, для которых $v$ является концевой вершиной. По определению, петля (ребро, соединяющее вершину саму с собой) вносит вклад, равный 2, в степень своей вершины.

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

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

Доказательство.

Для доказательства этого утверждения рассмотрим, как вычисляется сумма степеней всех вершин. При подсчёте этой суммы $\sum_{v \in V} \deg(v)$ мы учитываем вклад каждого ребра. Каждое ребро по определению имеет два конца.

Рассмотрим два возможных случая для любого ребра:

1. Ребро соединяет две различные вершины, например $u$ и $v$. В этом случае при подсчёте суммы степеней оно будет учтено один раз при вычислении степени вершины $u$ (добавит 1 к $\deg(u)$) и второй раз при вычислении степени вершины $v$ (добавит 1 к $\deg(v)$). Таким образом, его общий вклад в сумму степеней равен $1 + 1 = 2$.

2. Ребро является петлёй и соединяет вершину $w$ саму с собой. По определению, петля вносит вклад 2 в степень своей вершины. Таким образом, её вклад в общую сумму степеней также равен 2.

Поскольку каждое из $|E|$ рёбер графа, независимо от его типа, вносит в общую сумму степеней всех вершин вклад, равный ровно 2, то итоговая сумма равна числу рёбер, умноженному на 2. Следовательно, утверждение $\sum_{v \in V} \deg(v) = 2|E|$ является верным, что и требовалось доказать.

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