A counting version of Petersen's $2$-factor theorem
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 $\left((1 + o_r(1))\frac{2r}{e}\right)^n$ distinct $2$-factors. This improves the previously known lower bound $\left((1 + o_r(1))\frac{r}{e}\right)^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$.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.10424
curl -X POST /api/v1/records/arxiv/2610.10424/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.10424/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'