# Graphical Sequence Inequality

Let $$(d_1, \cdots, d_n)$$ be a graphical sequence, i.e. there exists a simple graph for which this sequence is its degree sequence. I want to show the following inequality for every $$k \in \{1, \cdots, n-1\}$$:

$$\sum_{i=1}^{k} d_i = k(k-1) + \sum_{i={k+1}}^n \min(k, d_i).$$

Here is my attempt: The assumption means that there exists an adjacency matrix $$A\in \{0,1\}^{n\times n}$$ with $$A_{ii} = 0$$ such that $$A^T = A$$ and $$\sum_j A_{ij} = d_i$$.

Now we can write:

$$\sum_{i=1}^{k} d_i = \sum_{i=1}^{k} \sum_{j=1}^n A_{ij} = \sum_{i=1}^{k} \sum_{j=1}^n A_{ij} = \sum_{i=1}^{k} \sum_{j=1}^k A_{ij} + \sum_{i=k+1}^{k} \sum_{j=1}^n A_{ij} \leq k(k-1) + \sum_{i=k+1}^{k} d_i$$

The first term is $$\leq k^2 - k$$ because each entry $$A_{ij}$$ is at most $$1$$ while the diagonal elements are $$0$$. But what am I missing, why do I just get the $$d_i$$ instead of $$\min(k, d_i)$$?

• I assume the $=$ is meant to be a $\leq$? Oct 12 '20 at 10:59
I don't think using the adjacency matrix is the easiest way to think of this, as it just adds a layer of extra abstraction to deal with. Rather consider a graph $$G=(V,E)$$ realising this sequence, and look at the set $$S = \{v_1, v_2, \dots, v_k\}$$ of vertices in $$G$$ such that $$deg(v_i) = d_i$$.
Each of the $$k$$ vertex in $$S$$ has at most $$(k-1)$$ neighbors in $$S$$, and so contributes at most $$(k-1)$$ to the sum $$\sum_{i=1}^{k}d_i$$. Further, each vertex $$v_j$$ of $$V-S$$ is adjacent to at most $$\min\{k, deg(v_j)\}$$ vertices of $$S$$, and so contributes at most $$\min\{k, deg(v_j)\}$$ to the sum $$\sum_{i=1}^{k}d_i$$