edited by
407 views
2 votes
2 votes

A sequence $d = (d_1,d_2,\dots , d_n)$ is graphic if there is a simple graph with degree sequence $d$

If $d = (d_1,d_2,d_3, \dots d_n)$ is graphic and $d_1 \geq d_2 \geq d_3 \geq \dots \geq d_n$ , then show that $\sum_{i=1}^{n}d_i$ is even and $$\sum_{i=1}^{k}d_i \leq \left [ k(k-1) + \sum_{i=k+1}^{n} \min\{k,d_i\} \right ] \quad ,1 \leq k \leq n$$.

edited by

Please log in or register to answer this question.

Related questions

2 votes
2 votes
0 answers
1
3 votes
3 votes
0 answers
3
dd asked Jul 1, 2017
382 views
Prove the following for graph $G$.When length of the shortest cycle in a graph is $k \geq 3$ and the minimum degree of the graph is $d$, then $G$ has minimum $\begin{alig...
15 votes
15 votes
3 answers
4
makhdoom ghaya asked Nov 14, 2016
1,851 views
Show that the number of odd-degree vertices in a finite graph is even.