Regular subgraphs of random graphs

In this paper, we prove that there exists a function ρ k = (4+o(1))k such that G(n, ρ/n) contains a k-regular graph with high probability whenever ρ \u3e ρ k. In the case of k = 3, it is also shown that G(n, ρ/n) contains a 3-regular graph with high probability whenever ρ \u3e λ ≈ 5.1494. These are the first constant bounds on the average degree in G(n, p) for the existence of a k-regular subgraph. We also discuss the appearance of 3-regular subgraphs in cores of random graphs. © 2006 Wiley Periodicals, Inc