Enumeration of the degree sequences of non-separable graphs and connected graphs

In 1962, S. L. Hakimi proved necessary and sufficient conditions for a given sequence of positive integers d1,d2,…,dnd1,d2,…,dn to be the degree sequence of a non-separable graph or that of a connected graph. Our goal in this note is to utilize these results to prove closed formulas for the functions dns(2m)dns(2m) and dc(2m)dc(2m), the number of degree sequences with degree sum 2m2m representable by non-separable graphs and connected graphs (respectively). Indeed, we give both generating function proofs as well as bijective proofs of the following identities: dns(2m)=p(2m)−p(2m−1)−∑j=0m−2p(j) and dc(2m)=p(2m)−p(m−1)−2∑j=0m−2p(j) where p(j)p(j) is the number of unrestricted integer partitions of jj.