The degree set of a finite simple graph $G$ is the set of distinct degrees of vertices of $G$. A theorem of Kapoor, Polimeni & Wall asserts that the least order of a graph with a given degree set $mathscr D$ is $1+max mathscr D$. Tripathi & Vijay considered the analogous problem concerning the least size of graphs with degree set $mathscr D$. We expand on their results, and determine the least size of graphs with degree set $mathscr D$ when (i) $min mathscr D mid d$ for each $d in mathscr D$; (ii) $min mathscr D=2$; (iii) $mathscr D={m,m+1,ldots,n}$. In addition, given any $mathscr D$, we produce a graph $G$ whose size is within $min mathscr D$ of the optimal size, giving a $big(1+frac{2}{d_1+1})$-approximation, where $d_1=max mathscr D$.
Download