On the Order of a Graph with a given Degree Set

Abstract

The degree set of a finite simple graph $G$ is the set of distinct degrees of vertices of $G$. For any given finite set $\mathcal{D}$ of positive integers, we determine all positive integers $n$ such that $\mathcal{D}$ is the degree set of some simple graph with $n$ vertices. This extends a theorem of Kapoor, Polimeni \& Wall (1977) which shows that the least such $n$ is $1+max(\mathcal{D})$.