Учебник «Вероятность и статистика. 7–9 классы», часть 1, с. 85, §19
№129. Докажите, что сумма степеней всех вершин графа вдвое больше числа рёбер в этом графе.
Дано:
граф с рёбрами
Доказать:
доказать, что сумма степеней всех вершин равна
Пусть в графе рёбер. Степень вершины — это число выходящих из неё рёбер. Нам нужно доказать, что сумма степеней всех вершин равна .
Способ подсчёта. Возьмём любое ребро. У него два конца — две вершины, которые оно соединяет. Это ребро выходит из каждой из своих двух вершин, поэтому оно учтено ровно два раза: один раз в степени одной вершины и один раз в степени другой. Так же будет с каждым ребром графа.
Итак, когда мы складываем степени всех вершин, то каждое ребро посчитано ровно два раза. Рёбер , поэтому сумма степеней равна , то есть вдвое больше числа рёбер.
Что делать с петлёй? Петля — ребро, которое начинается и заканчивается в одной и той же вершине. Оба её конца в одной вершине, и при подсчёте степени такое ребро считается дважды (п. 19). Значит, и петля вносит в сумму степеней ровно 2, и рассуждение остаётся верным.
Пример. В графе на рисунке (это граф с рисунка 13) шесть рёбер, а степени вершин равны 2, 3, 3, 2, 1, 1. Складываем: .
Следствие. Раз сумма степеней равна , она всегда чётна. Отсюда следует и свойство из п. 19: количество вершин нечётной степени в любом графе чётно.
Ответ: Доказано: каждое ребро входит в степени ровно двух своих концов (петля — дважды в одной вершине), поэтому сумма степеней всех вершин равна , где — число рёбер.
