Extreme degree sequences of simple graphs

AbstractErdös and Gallai characterize in [3] the sequences of integers which are degree sequences of a simple graph, in terms of a system of (linear) inequalities. The set of all real n-vectors satisfying these inequalities is a convex polytope Kn. In this paper we study the properties of Kn. In particular, we show that its vertices are precisely the sequences which are degree sequences of a unique graph (Theorem 1). We also give a full description of the vertices of Kn (Theorem 2)