6. Задача повышенной сложности: дан граф \(G\subseteq N\) вершинами. Докажи, что сумма степеней всех вершин графа равна удвоенному количеству рёбер.

В условии число вершин после знака \(\subseteq\) обрезано: «дан граф \(G\subseteq N\) вершинами». Для общего доказательства конкретное число вершин не требуется, поэтому докажем утверждение для любого конечного неориентированного графа.

1. Посчитаем вклад каждого ребра в сумму степеней всех вершин.
2. У каждого ребра ровно два конца. Оно добавляет по единице к степени каждой из двух вершин, поэтому его общий вклад в сумму степеней равен 2.
3. Если рёбер \(m\), то суммарный вклад всех рёбер равен \(2m\). Это и есть сумма степеней вершин.

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