Let n N and d₁ d₂ dₙ 1 be integers. There is characterization of when (d₁, d₁, , dₙ) 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 which perfect matchings can be realized in the labelled graph? Here we find the extremal answers to this question, showing that the sequence (d₁, d₂, , dₙ): (1) can realize a perfect matching iff it can realize \ (1, n), (2, n-1), , (n/2, n/2+1) \, and; (2) can realize any perfect matching iff it can realize \ (1, 2), (3, 4), , (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.
Briggs et al. (Wed,) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: