Perfect matchings in random subgraphs of regular bipartite graphs

Consider the random process in which the edges of a graph G are added one by one in a random order. A classical result states that if G is the complete graph K 2 nor the complete bipartite graph K n , n , then typically a perfect matching appears at the moment at which the last isolated vertex disappears. We extend this result to arbitrary k ‐regular bipartite graphs G on 2 n vertices for all k = ω ( n log 1 / 3 n ) . Surprisingly, this is not the case for smaller values of k . Using a construction due to Goel, Kapralov, and Khanna, we show that there exist bipartite k ‐regular graphs in which the last isolated vertex disappears long before a perfect matching appears.