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

3 Сформулируйте теорему о сумме степеней вершин.

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

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

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

Доказательство
Рассмотрим процесс подсчёта суммы степеней всех вершин. Степень вершины — это число рёбер, для которых эта вершина является конечной. Каждое ребро графа по определению соединяет две вершины (или является петлей, соединяющей вершину саму с собой).

• Каждое ребро, не являющееся петлей, соединяет две различные вершины. Следовательно, оно вносит вклад, равный 1, в степень каждой из двух своих концевых вершин. Таким образом, при суммировании степеней это ребро будет посчитано ровно дважды.
• Каждая петля инцидентна только одной вершине, но по определению она добавляет 2 к степени этой вершины. Таким образом, петля также учитывается дважды в общей сумме степеней.

Поскольку каждое ребро вносит вклад, равный 2, в общую сумму степеней вершин, то сумма степеней всех вершин равна удвоенному числу рёбер.

Следствие из теоремы
Важным следствием этой теоремы является то, что в любом графе число вершин с нечётной степенью должно быть чётным. Это объясняется тем, что общая сумма степеней всех вершин ($2|E|$) всегда является чётным числом. Эту сумму можно разбить на две части: сумму степеней вершин с чётной степенью и сумму степеней вершин с нечётной степенью. Сумма любого количества чётных чисел всегда чётна. Чтобы общая сумма была чётной, сумма нечётных степеней также обязана быть чётной. А сумма нечётных чисел будет чётной тогда и только тогда, когда их количество (т.е. число вершин с нечётной степенью) чётно.

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