Regulární graf

V teorii grafů je regulární graf takový graf, jehož všechny vrcholy mají stejný stupeň. Regulární graf s vrcholy, které mají stupeň k se nazývá k-regulární.

Regulární grafy stupně nejvýše 2 lze jednoduše popsat: 0-regulární graf se skládá ze samostatných vrcholů (bez hran), 1-regulární ze samostatných hran a 2-regulární ze samostatných cyklů. 3-regulární graf se nazývá kubický.

0-regulární graf

1-regulární graf

2-regulární graf

Silně regulární graf je takový graf, v němž má každá dvojice sousedních vrcholů stejný počet k společných sousedů a každá dvojice nesousedních vrcholů stejný počet n společných sousedů. Nejmenší regulární graf, který není silně regulární, je cyklický graf na 6 vrcholech.

Úplný graf K_n je silně regulární pro libovolné n.