Problem
COM-B2-M01-P019 Many Paths of Length Two
A graph has \(n\) vertices and \(m\) edges. Prove that the number of length-\(2\) paths is at least \(n\binom{\frac{2m}{n}}{2}\), where \(\binom{x}{2}=\frac{x(x-1)}2\). Explain why this implies: if the average degree is greater than \(r\), then some vertex lies in more than \(\binom r2\) length-\(2\) paths as the middle vertex.
Use convexity of \(\binom{x}{2}\) and \(\sum d_i=2m\).
The number of length-\(2\) paths is \(\sum_i\binom{d_i}{2}\), where \(d_i\) are vertex degrees. The function \(\binom{x}{2}=\frac{x(x-1)}2\) is convex, so for fixed sum \(\sum d_i=2m\), the sum \(\sum\binom{d_i}{2}\) is at least \(n\binom{2m/n}{2}\). If the average degree \(\frac{2m}{n}>r\), then the average value of \(\binom{d_i}{2}\) is greater than \(\binom r2\) in the needed strict sense, so some vertex contributes more than \(\binom r2\) length-\(2\) paths.
This problem requires a careful discussion of convexity; it can also be proved by smoothing degrees.