Um grafo $G = (V,A)$ é dito $k-$regular se todos os seus vértices possuem grau $k$. Em outras palavras, um grafo é dito regular se todos os seus vértices possuem o mesmo grau.