Graphical sequences and plane trees

Balister, the second author, Groenland, Johnston, and Scott recently showed that there are asymptotically C4ⁿ/n3/4 many unordered sequences that occur as degree sequences of graphs with n vertices. Combining limit theory for infinitely divisible distributions with a new connection between a class of random walk trajectories and a subset counting formula from additive number theory, we describe C in terms of Walkup’s number of rooted plane trees. The bijection is related to an instance of the Lévy–Khintchine formula. Our main result complements a result of Stanley, that ordered graphical sequences are related to quasi-forests.