= Solution
Begin with the <configuration model> for $n$ labelled vertices of degree $r$. Let $Y_\ell$ count <cycles in a graph> with specified paired edges, so parallel-edge choices are counted separately before conditioning. Choose a cyclic ordering of $\ell$ distinct vertices in $(n)_\ell/(2\ell)$ ways, where division by $2\ell$ removes rotation and reversal. At each vertex choose an ordered pair of distinct <half-edges> for the entering and leaving edges, in $r(r-1)$ ways. These $\ell$ prescribed pairs appear with the pairing probability from part (i), giving
$$
\mathbb EY_\ell=\frac{(n)_\ell}{2\ell}\frac{[r(r-1)]^\ell}{(rn-1)(rn-3)\cdots(rn-2\ell+1)}\longrightarrow\frac{(r-1)^\ell}{2\ell}.
$$
It remains to justify conditioning on simplicity: merely dividing by a positive simplicity probability would give an incorrect constant.
Unconditionally, part (i) with no forbidden graph has $\lambda=r-1$, so
$$
\Pr(\text{simple})=\exp\left(-\frac{r-1}{2}-\frac{(r-1)^2}{4}\right)+o(1).
$$
Condition on one specified cycle pairing. The unpaired half-edges form a uniform <configuration model> with degree $r-2$ at its $\ell$ vertices and degree $r$ elsewhere. A completion of the full graph is simple exactly when the residual graph is simple and has no additional edge along one of the already prescribed cycle edges. This forbidden graph has <maximum degree> two. Because $r,\ell$ are fixed,
$$
M'=rn-2\ell,\qquad \lambda'=r-1+O(1/n),\qquad \mu'=O(1/n).
$$
After permuting labels if needed to sort the degrees, the assumptions of part (i) still hold, including residual degrees at least one. Its <bounded-degree pairing avoidance estimate> therefore shows that
$$
\frac{\Pr(\text{simple}\mid\text{specified cycle pairs})}{\Pr(\text{simple})}\longrightarrow1.
$$
This ratio is the same for each prescribed cycle, by symmetry. Sum over their indicators to obtain $\mathbb E(Y_\ell\mid\text{simple})=(1+o(1))\mathbb EY_\ell$. Conditioning is uniform over all simple $r$-regular graphs because each has $(r!)^n$ pairing representations. On simplicity, $Y_\ell$ is the ordinary cycle count. Hence the <short-cycle expectation in a uniform regular graph> is
$$
\boxed{\mathbb E C_\ell(G_{n,r\text{-reg}})\longrightarrow\frac{(r-1)^\ell}{2\ell}.}
$$
Back to article page
