-
Per rispondere alla domanda, analizziamo un grafo con n vertici e m lati. Indichiamo con *di il grado del vertice i, ossia il numero di lati che partono da questo vertice. La somma ∑i=1ndi\sum_{i=1}^{n}d_i dei gradi dei vertici vale 2m poiché ogni lato (i, j) è conteggiato a entrambi i suoi estremi i e j*. La disuguaglianza di Cauchy‒Schwarz dà:
∑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}.
Ora serve un po’ di astuzia. Sommare i quadrati dei gradi dei vertici significa contare il grado di ciascun vertice tante volte quanti sono i lati che partono da quel vertice. Un altro modo di ottenere questo totale consiste nel sommare le quantità *di + dj per tutte le coppie (i, j*) corrispondenti a un lato del grafo.