-
Para responder a la pregunta, analicemos un grafo de n vértices y m aristas. Denotemos por *di el grado del vértice i, es decir, el número de aristas que parten de ese vértice. La suma ∑i=1ndi\sum_{i=1}^{n}d_i de los grados de los vértices es igual a 2m, pues cada arista (i, j) se cuenta en cada uno de sus extremos i y j*. La desigualdad de Cauchy-Schwarz da:
∑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}.
Ahora hace falta un poco de ingenio. Sumar los cuadrados de los grados de los vértices equivale a contar el grado de cada vértice tantas veces como aristas parten de él. Otra forma de obtener este total consiste en sumar *di + dj para cada par (i, j*) que corresponde a una arista del grafo.