Теория на графи - Graphic Sequence

[mrgray]

Имаме [tex]d = (d_1, d_2, d_3, ..., d_n)[/tex], където [tex]d_1, ..., d_n[/tex] са degrees на върховете в прост граф. Също [tex]d_1 \ge d_2 \ge ... \ge d_n[/tex]. Трябва да докажем:

[tex]\sum_{i=1}^{k}d_i = k(k-1) + \sum_{i=k+1}^{n}min(k, d_i)[/tex], [tex]1 \le k \le n[/tex],

където n е брой на върховете.