Problem
COM-B2-M01-P007 A Large Degree
#7
★★★☆☆ Level 3 of 5
A simple graph has \(n\) vertices and more than \(\frac{(r-1)n}{2}\) edges. Prove that some vertex has degree at least \(r\).
Use the sum of degrees.
The sum of degrees is \(2E>(r-1)n\). If all degrees were at most \(r-1\), the sum of degrees would be at most \((r-1)n\), a contradiction. Hence some vertex has degree at least \(r\).
The basic form of “average greater than \(r-1\)”.