Degree sequences realizing labelled perfect matchings

Abstract

Let $n\in \mathbb{N}$ and $d_1\ge d_2\ge d_n\ge 1$ be integers. There is characterization of when $(d_1,d_1,\dots ,d_n)$ is the degree sequence of a graph containing a perfect matching, due to results of Lovász (1974) and Erdős and Gallai (1960). But \emph{which} perfect matchings can be realized in the labelled graph? Here we find the extremal answers to this question, showing that the sequence $(d_1,d_2,\dots ,d_n)$: (1) can realize a perfect matching iff it can realize $\{(1,n),(2,n-1),\dots ,(n/2,n/2+1)\}$, and; (2) can realize any perfect matching iff it can realize $\{(1,2),(3,4),\dots ,(n-1,n)\}$. Our main result is a characterization of when (2) occurs, extending the work of Lovász and Erdős and Gallai. Separately, we are also able to establish a conjecture of Yin and Busch, Ferrera, Hartke, Jacobsen, Kaul, and West about packing graphic sequences, establishing a degree-sequence analog of the Sauer-Spencer packing theorem. We conjecture an $h$-factor analog of our main result, and discuss implications for packing $h$ disjoint perfect matchings.