Problem
COM-B2-M01-P015 Paths of Length Two
#15
★★★★☆ Level 4 of 5
In a graph, the vertex degrees are \(d_1,\ldots,d_n\). Prove that the number of unordered paths of length \(2\) is \(\sum_{i=1}^n\binom{d_i}{2}\).
Each length-\(2\) path has a unique middle vertex.
Fix the middle vertex \(v_i\). To form a length-\(2\) path with this middle vertex, choose two distinct neighbours among its \(d_i\) neighbours: \(\binom{d_i}{2}\) ways. Each unordered length-\(2\) path has exactly one middle vertex, so summing over all vertices gives the exact number.
This is an important bridge to Book 2 graph problems.