-
To answer the question, let us analyze a graph with n vertices and m edges. Let *di be the degree of vertex i, that is, the number of edges incident with that vertex. The sum ∑i=1ndi\sum_{i=1}^{n}d_i of the vertex degrees is 2m, since each edge (i, j) is counted at both of its endpoints, i and j*. The Cauchy–Schwarz inequality gives:
∑i=1ndi=∑i=1n1×di⩽∑i=1n12×∑i=1ndi2=n∑i=1ndi2.\sum_{i=1}^{n}d_i=\sum_{i=1}^{n}1\times d_i\leqslant \sqrt{\sum_{i=1}^{n}1^2\times \sum_{i=1}^{n}d^2_i}= \sqrt{n\sum_{i=1}^{n}d^2_i}.
A little ingenuity is now required. Adding the squares of the vertex degrees amounts to counting each vertex's degree once for every edge incident with that vertex. Another way to obtain the same total is to add the sums *di + dj over all pairs (i, j*) corresponding to an edge of the graph.