-
Pour répondre à la question, analysons un graphe à n sommets comprenant m arêtes. Notons di le degré du sommet i, c’est-à-dire le nombre d’arêtes qui partent de ce sommet. La somme ∑i=1ndi\sum_{i=1}^{n}d_i des degrés des sommets vaut 2m car chaque arête (i, j) est comptabilisée à chacune de ses extrémités i et j. L’inégalité de Cauchy‒Schwartz donne :
∑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}.
Il faut maintenant un petit peu d’astuce. Additionner les carrés des degrés des sommets, c’est compter le degré de chaque sommet autant de fois qu’il y a d’arêtes qui partent de ce sommet. Une autre façon d’obtenir ce total est d’additionner des sommes di + dj pour tous les couples (i, j) correspondant à une arête du graphe.