Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
This paper establishes a quantitative version of Petersen's theorem by proving 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 result significantly improves the prior lower bound by a factor of $2^{(1 + o(1))n}$ and is asymptotically tight for large $r$. Furthermore, the work derives asymptotically tight bounds on the number of $2$-factorizations for such graphs.
Nearly doubling the number of distinct 2-factors in regular graphs reveals a richer combinatorial structure than previously understood.
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$.