Graph Theory k-Regular Graph A k-regular graph is a graph in which all vertices have degree k. Related Complete Graph