How to choose a $d$-regular graph on $n$ vertices uniformly at random? Let $n\geq 1$ be an even number and $d\geq 1$ be integers.
In these notes by Luca Trevisan, we see a procedure of coming up with a $d$-regular on $n$ vertices on the first page.
The procedure is: Let $V=\{1, 2, 3, \ldots, n\}$.

Choose $d$ perfect matchings on $V$ (uniformly?) at random and take the union of these matchings.

It is not clear as to how this procedure gives rise to a $d$-regular graph. Two different matchings can share an edge. So unless we are allowing multiple edges (which I am pretty sure we are not), this does not seem to make sense.
Can somebody clarify what is happening here?
 A: It's possible that the idea in the lecture notes is just to allow parallel edges. But we can achieve an actual reasonable distribution with the same properties by sampling a union of $d$ disjoint matchings, chosen uniformly at random. In practice, this can be done by picking $d$ matchings uniformly and rejecting if an edge appears in more than one of them. 
(Note that by default, we must start over from the beginning if this happens; the similar-looking algorithm which goes through the matchings one at a time, and keeps sampling the $i^{\text{th}}$ matching until it is disjoint from the previous $i-1$, does not produce the same distribution. No idea if it produces a sufficiently similar distribution to be worth doing anyway.)
This is a reasonable model for two reasons:


*

*The failure probability is not too high; with a constant probability depending on $d$, a uniformly chosen set of $d$ matchings is disjoint. 

*The model is contiguous to the uniform: a statement holds with probability tending to $1$ in this model, if and only if it holds with probability tending to $1$ for a uniformly chosen $d$-regular graph. (In both cases, as $n \to \infty$.)


Regarding the first point: the probability that two uniformly chosen edges are equal is $\frac{1}{\binom n2} \sim \frac{2}{n^2}$. In the union-of-$d$-matchings model, there are $\binom d2 n^2$ pairs of edges we have to worry about, so the expected number of collisions is $\binom d2 n^2 \cdot \frac{2}{n^2} = d(d-1)$. These collisions are so close to independent that their distribution is asymptotically Poisson; in particular, the chance of getting no collisions is $e^{-d(d-1)}+o(1)$. This may seem bad, but it is remarkable in that the limit does not depend on $n$.
Regarding the second point: there are several such contiguity results known, which are summarized in these slides. Let $\mathcal G_{n,d}$ be the uniform distribution on $d$-regular graphs. Then the relevant result from these slides is that $\mathcal G_{n,d}$ is contiguous with $\mathcal G_{n,d-1} \oplus \mathcal G_{n,1}$ for all $d\ge 2$, where $\oplus$ denotes this try-it-until-it-works disjoint superposition. As a corollary, $\mathcal G_{n,d}$ is contiguous with $\mathcal G_{n,1}^{\oplus d}$, which is the model used here - because $\mathcal G_{n,1}$ is precisely a uniformly chosen matching.
In particular, though this does not appear to be mentioned in those lecture notes (yet?), proving an a.a.s. expansion result for $\mathcal G_{n,1}^{\oplus d}$ is the same as proving it for $\mathcal G_{n,d}$. 
Moreover, proving this result in the union-of-matchings model without resampling if the matchings fail to be disjoint also achieves the same result. Conditioning on an event with probability $e^{-d(d-1)}$ can increase the probability that the graph is not an expander by at most a factor of $e^{d(d-1)}$, and $e^{d(d-1)} \cdot O(\frac{1}{n^2})$ is still $O(\frac{1}{n^2})$.
A: I can only assume that they consider $n$ to be much bigger than $d$. In that case, the chance of matchings overlapping is sufficiently small, so that you can assume that they don't (or you compute a few more until they don't, if needed).
It is common in some lectures, especially more practical ones, to neglect such special cases, given that their chance is small enough; although that is sometimes hard to get used to coming from a strong theoretical, mathematical background.
