The classical theory of Erdős–Rényi random graphs is concerned primarily with random subgraphs of K_n or K_{n,n}. Lately, there has been much interest in understanding random subgraphs of other graph families, such as regular graphs. We study the following problem: Let G be a k-regular bipartite graph with 2n vertices. Consider the random process where, beginning with 2n isolated vertices, G is reconstructed by adding its edges one by one in a uniformly random order. An early result in the theory of random graphs states that if G=K_{n,n}, then with high probability a perfect matching appears at the same moment that the last isolated vertex disappears. We show that if k = Ω(n) then this holds for any k-regular bipartite graph G. This improves on a result of Goel, Kapralov, and Khanna, who showed that with high probability a perfect matching appears after O(n log(n)) edges have been added to the graph. On the other hand, if k = o(n / (log(n) log log(n))), we construct a family of k-regular bipartite graphs in which isolated vertices disappear long before the appearance of perfect matchings. Joint work with Roman Glebov and Zur Luria.