The first k-regular subgraph is large