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