Problem
COM-B1-M09-P018 The Part with Five Vertices
#18
★★★☆☆ Level 3 of 5
In a bipartite graph, the parts have sizes \(5\) and \(7\), and there are \(20\) edges. Prove that in the part of size \(5\), some vertex has degree at least \(4\).
Compute the average degree in that part.
Each edge is incident to exactly one vertex in the part of size \(5\). Therefore the sum of degrees in this part is \(20\). The average degree is \(20/5=4\). Hence at least one vertex has degree at least \(4\).
Average inside one part is often stronger than global average.