Regular subgraphs of random graphs

In this paper, we prove that there exists a function rho(k) = (4+o(l))k such that G(n, rho/n) contains a k-regular graph with high probability whenever rho > rho(k). In the case of k 3, it is also shown that G(n, rho/n) contains a 3-regular graph with high probability whenever p > approximate to 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. (c) 2006 Wiley Periodicals, Inc.