Регулярен граф

Регулярен граф (още правилен граф, еднороден граф) е термин от теорията на графите, с който се означава граф, при който всеки връх има равен брой съседни върхове, т.е. всички върхове на графа са от една и съща степен.

Тривиалният случай на регулярен граф от нулева степен е граф, състоящ се само от множество върхове, несвързани с ребра (празен граф). Регулярният граф от първа степен се състои от несвързани помежду си ребра. Малко по-сложен е случаят при регулярен граф от степен 2, тъй като графът може да е безкраен или краен, като крайният граф може да е свързан или несвързан. Краен свързан регулярен граф от втора степен се нарича цикъл.

За регулярните графи са в сила следните твърдения (теореми):

Броят на върховете на краен регулярен граф от нечетна степен е винаги четно число.
За краен регулярен граф от степен k с m на брой върхове, броят на ребрата M = k.m / 2.
За всяко четно естествено число m ≥ 4 съществува краен регулярен граф от трета степен с m на брой върхове.
Всеки краен регулярен граф от степен k с 2k + 1 върха съдържа Хамилтонов цикъл. (Теорема на Криспин Наш-Уилямс)