Докажите, что сумма степеней всех вершин графа вдвое больше числа рёбер в этом графе.
Решение
Пусть в графе m рёбер. Степень каждой вершины по определению § равна числу концов рёбер, находящихся в этой вершине. Сложим степени всех вершин. Обычное ребро при этом будет посчитано дважды: один раз у первого конца и один раз у второго. Если ребро является петлёй, оба конца совпадают, но по правилу § петля тоже прибавляет к степени своей вершины . Значит, каждое из m рёбер даёт в общую сумму ровно . Получаем . Это и требовалось доказать.
Ответ
Сумма степеней всех вершин равна , где m — число рёбер.
Помогло?
Нет твоего задания?Сфоткай, и ДЗмэн решит за пару секунд.
