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}) \).