Задача
COM-B2-M01-P015 Пути длины два
#15
★★★★☆ Уровень 4 из 5
В графе степени вершин равны \(d_1,\ldots,d_n\). Докажите, что число неупорядоченных путей длины \(2\) равно \(\sum_{i=1}^n\binom{d_i}{2}\).
Каждый путь длины \(2\) имеет единственную среднюю вершину.
Зафиксируем среднюю вершину \(v_i\). Чтобы получить путь длины \(2\) с этой средней вершиной, надо выбрать две различные соседние вершины из \(d_i\) соседей: \(\binom{d_i}{2}\) способов. Каждый неупорядоченный путь длины \(2\) имеет ровно одну среднюю вершину, значит сумма по всем вершинам даёт точное число таких путей.
Это важный мост к графовым задачам Book 2.