Upper bound on the sum of degrees of k vertices out of total n vertices

Question

I have show the first part (which is off course the easiest part), But I need to know how to find this upper bound on the sum of degrees of k vertices out of total n vertices.

Answer 1

Hints: First, think about counting the number of edges between the first $k$ nodes. How does that relate to the first term on the right hand side? (You'll need to account for a factor of $2$ here...)

Next, think about counting the number of edges between the first $k$ nodes and each of the last $n-k$ nodes. How many can there be, and how does that relate to the sum on the right side? (When you're counting this case, will you need a factor of $2$?)