Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 15 min ago
PreprintarXiv licencearXiv

A counting version of Petersen's $2$-factor theorem

  • Hyunwoo Lee
Open at sourcePDFDOICite

Abstract

A classical result of Petersen states that every regular graph of even degree has a $2$-factor. We prove that every n-vertex 2r-regular simple graph contains at least ((1 + or(1))2r/e)n distinct $2$-factors. This improves the previously known lower bound ((1 + or(1))r/e)n by a factor of 2(1 + o(1))n and is asymptotically tight for large r. As a direct consequence, we determine asymptotically tight bounds on the number of $2$-factorizations of a given 2r-regular simple graph for every sufficiently large r.

Related

  1. A topological version of Huber's theorem
    Ara Basmajian, Hugo Parlier
    arXivPreprintarXiv licenceFull textGeometry & topologyarXiv
  2. On the causality of gravitational pp-wave spacetimes: A null version of Anderson's rigidity theorem
    Hannah Cairo
    arXivPreprintarXiv licenceFull textGeometry & topologyGravitation & general relativityarXiv
  3. A graded version of the separator theorem for planar graphs
    Nabil H. Mustafa, Janos Pach
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. On the large-clique version of the Erdős-Sós theorem
    Kun Cheng, Yurui Tang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. A positive version of Miljutin's Theorem
    Javier Laguna-Ricart, Gonzalo Martínez-Cervantes, Jakub Rondoš +1
    arXivPreprintarXiv licenceFull textAnalysis & PDEsarXiv

Cite

BibTeXRIS
BibTeX
@misc{lee2026counting,
  title = {{A counting version of Petersen's $2$-factor theorem}},
  author = {Hyunwoo Lee},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.10424},
  eprint = {2610.10424},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.10424},
}
RIS
TY  - UNPB
TI  - A counting version of Petersen's $2$-factor theorem
AU  - Hyunwoo Lee
PY  - 2026
DA  - 2026/10/07
PB  - arXiv
DO  - 10.48550/arxiv.2610.10424
UR  - https://arxiv.org/abs/2610.10424
AB  - A classical result of Petersen states that every regular graph of even degree has a $2$-factor. We prove that every n-vertex 2r-regular simple graph contains at least ((1 + o_r(1))2r/e)^n distinct $2$-factors. This improves the previously known lower bound ((1 + o_r(1))r/e)^n by a factor of 2^(1 + o(1))n and is asymptotically tight for large r. As a direct consequence, we determine asymptotically tight bounds on the number of $2$-factorizations of a given 2r-regular simple graph for every sufficiently large r.
ER  -