Connectivity of random regular multigraphs For even integers $n$ and integers $3\le r < n$, is it true that a random $r$-regular multigraph on $n$ labelled vertices, obtained as the union of $r$ independent uniformly random perfect matchings, is asymptotically almost surely connected?
I know this is true if one conditions on there being no multiple edges, but does connectivity still hold without this condition?
 A: In any perfect matching, there are $\binom{n/2}{k}$ vertex sets of size $2k$ with no edges to their complement: just take any $k$ edges. To phrase this probabilistically: a fixed set of $2k$ vertices has a probability of exactly $\frac{\binom{n/2}{k}}{\binom{n}{2k}}$ of having no edges to its complement in a uniformly random perfect matching. So the expected number of such sets in a random union of three matchings is
$$
    \sum_{k=1}^{n/2-1} \binom{n}{2k} \left(\frac{\binom{n/2}{k}}{\binom{n}{2k}}\right)^3 =  \sum_{k=1}^{n/2-1}  \frac{\binom{n/2}{k}^3}{\binom{n}{2k}^2}.
$$
The $k=1$ term of this sum is $\frac{(n/2)^3}{\binom n2^2} = O(\frac1n)$. The $k=2$ term is $O(\frac1{n^2})$.
To deal with the other terms, figure out the ratio between consecutive terms. We have
$$
   \frac{\binom{n/2}{k+1}}{\binom{n/2}{k}} = \frac{n/2-k}{k+1} \qquad \text{ and } \qquad \frac{\binom n{2k+2}}{\binom n{2k}} = \frac{(n-2k)(n-2k-1)}{(2k+1)(2k+2)}
$$
and therefore
$$
    \frac{\binom{n/2}{k+1}^3 / \binom{n}{2k+2}^2}{\binom{n/2}{k}^3 / \binom n{2k}^2} = \frac{(n/2-k)(2k+1)^2}{(n-2k-1)^2(k+1)} < \frac{(n-2k)(2k+1)}{(n-2k-1)(n-2k-1)}
$$
which is less than $1$ provided that $2k+1 \le n-2k-2$, or $4k+3 \le n$.
We could get worried at that point, except that the sum is symmetric around $k = \frac n4$, and when $k$ is close to $\frac n4$, the ratio $\binom{n/2}{n/4}^3 / \binom{n}{n/2}^2$ is exponentially small: close to $2^{-n/2}$. So the first and last terms are $O(\frac1n)$, and the other $n$ terms are $O(\frac1{n^2})$ at worst; therefore the whole sum is $O(\frac1n)$.
In particular, the expected number of such sets is $O(\frac1n)$, so whp there are no such sets, and the multigraph is connected.
