



 
Hi, If the minimum degree of G is also k, then G is itself kregular. Otherwise, make two copies G', G'' of G, and for every vertex u of G of degree less than k, join its copy u' in G' to its copy u'' in G''. Prove that the resulting graph is bipartite, and that its minimum degree is one more than that of G. Do you see how that helps? Claude  


Math Central is supported by the University of Regina and The Pacific Institute for the Mathematical Sciences. 