Граф называется регулярным графом валентности $k$, если степень каждой его вершины равна $k$.