Building Large k-Cores from Sparse Graphs