Let G = (V, E) be an undirected graph (and while it should go without saying, G has no self-loops or parallel edges). As always, let n denote the number of vertices in the graph, and m denote the number of edges; that is, n = |V and m = E.

(a) Use the extended Pigeonhole principle to prove that there is some vertex v € V

with degree (v) > [2m/n].

(b) Use part (a) to show that m < n(n-1)/2