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)$?

Thank you in advance!

  • $\begingroup$ I assume the $=$ is meant to be a $\leq$? $\endgroup$ 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$.

Click the spoiler below for an outline of a proof:

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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.