I am trying to solve the following problem:
A sequence $(d_1,\ldots,d_n)$ is said to be a graphic sequence if there exists a simple graph $G$ such that the degrees of $G$ are exactly $d_1,\ldots,d_n$. If $D$ is a graphic sequence such that $d_1 \geq \cdots \geq d_n$, then:
- $\sum_{i=1}^n d_i$ is even
- $\sum_{i=1}^k d_i \leq k(k-1) + \sum_{i=k+1}^n \min(k,d_i)$
I could easily prove the first property since I've used the fact that if $m$ is the number of edges of $G$, then $$\sum_{v \in G} d(v) = 2m$$
Now, I've tried to show that the second property holds with an inductive proof but I got stuck in the inductive step: if $(d_1,\ldots,d_{n+1})$ is a graphic sequence and $d_{n+1}$ is odd, then I cannot apply the inductive hypothesis on $(d_1,\ldots,d_n)$ since its sum is odd.
Any ideas to prove this property ? Maybe there is an alternative solution without induction, I would appreciate if someone could give me any suggestions. Thanks in advance !
Let $v_1, v_2, \dots, v_n$ be vertices of degree $d_1, d_2, \dots, d_n$ in a graph with this degree sequence, and let $S = \{v_1,v_2,\dots,v_k\}$. Write $\deg_S(v_i)$ for the number of neighbors a vertex has in $S$. $$ \sum_{i=1}^k d_i = \sum_{i=1}^n \deg_S(v_i) $$ by double-counting: both sides count the number of endpoints all edges of the graph have in $S$.
To prove the inequality $$\sum_{i=1}^k d_i \leq k(k-1) + \sum_{i=k+1}^n \min\{k,d_i\},$$ it's enough to show that $$ \deg_S(v_i) \le \begin{cases} k-1 & v_i \in S \\ \min\{k,d_i\} & v_i \notin S \end{cases} $$ and apply this bound to every vertex.