# pr.probability – Contiguity of uniform random regular graphs and uniform random regular graphs which have a perfect matching

Let us consider $$cal{G}_{_{n,d}}$$ as the uniform probability space of d-regular graphs
on the n vertices $${1, ldots, n }$$ (where $$dn$$ is even). We say that an event $$H_{_{n}}$$ occurs a.a.s. (asymptotically almost surely) if $$mathbf{P}_{_{cal{G}}}(H_{_{n}}) longrightarrow 1$$ as $$n ⟶ infty$$.

Also, suppose $$(cal{G}_{_{n}})_{_{n ≥ 1}}$$ and $$(cal{hat{G}}_{_{n}})_{_{n ≥ 1}}$$ are two sequences of probability spaces such that $$cal{G}_{_{n}}$$ and $$cal{hat{G}}_{_{n}}$$ are differ only in the probabilities. We say that these sequences are contiguous if a sequence of events $$A_{_{n}}$$ is a.a.s. true in $$cal{hat{G}}_{_{n}}$$ if and only if it is true in $$cal{hat{G}}_{_{n}}$$, in which case we write
$$cal{G}_{_{n}} approx cal{hat{G}}_{_{n}}.$$

Thorem. (Bollobas) For any fixed $$d geq 3$$, $$G_{_{n}} ∈ cal{G}_{_{n,d}}$$ a.a.s has a perfect matching.

Using $$cal{G}^p_{_{n,d}}$$ to denote the uniform probability space of d-regular graphs which have a perfect matching on the n vertices $${1, ldots, n }$$, is it true to conclude from the above theorem that $$cal{G}_{_{n,d}} approx cal{G}^p_{_{n,d}}$$?

Posted on