Некоторые свойства регулярных графов:

• Равенство степеней всех вершин. 24 Регулярный граф — это граф, в котором каждая вершина имеет одинаковое количество соседей. 24
• Теорема Нэш-Вильямса. 24 Каждый k-регулярный граф на 2k + 1 вершинах имеет гамильтонов цикл. 24
• Для графа нечётной степени количество вершин должно быть чётным. 13
• Полный граф из N вершин является (N - 1) регулярным. 1 В таком графе каждая вершина соединена со всеми (N - 1) оставшимися вершинами, поэтому степень каждой из них равна (N - 1). 1
• Цикл всегда является 2-регулярным. 1 В цикле каждая вершина имеет двух соседей, поэтому такой граф является 2-регулярным. 1
• Число рёбер k-регулярного графа с N вершинами равно (N * K) / 2. 1