The polytope of degree sequences

AbstractA nonnegative integer sequence (d1,d2,…,dn) is called a degree sequence if there exists a simple graph on the vertex set V= {1,2,…,n} such that deg(i)= di for all i. The degree sequence of a threshold graph is a threshold sequence. Let Dn= Convex Hull {(x1,x2,…,xn)|(x1,…,xn) is a degree sequence}. It is proved that: (1) A degree sequence f is an extreme point of Dn if and only if f is a threshold sequence. (2) Two threshold sequences f and g are adjacent extreme points of Dn if and only if f can be obtained from g by either adding 1 to two components of g or subtracting 1 from two components of g. (3) Dn is determined bythe following system of inequalities:∑i∈xi−∑i∈Txi⩽|S|(n−1−|T|) for all sets S, T with ⊘ ≠ S ∪ T ⊆ {1,2,…,n}, S ∩T = ⊘. Moreover, this system is totally dual integral. Furthermore, for n ⩾ 4, (S,T) determines a facet of Dn if and only if either ⋎S ∪ T| = 1 or else S ≠ ⊘,T ≠ ⊘, |S ∪T| ≠n - 1,n - 2. (4) f is a threshold sequence if and only if the only degree sequences majorizing f in the sense of Hardy, Littlewood, and Pólya are the rearrangements of f. Consequently, every degree sequence is a convex combination of isomorphic threshold sequences (i.e., threshold sequences that are rearrangements of each other)