Graf regularny

Graf regularny stopnia ${\displaystyle n}$ to graf, w którym wszystkie wierzchołki są stopnia ${\displaystyle n,}$ czyli z każdego wierzchołka grafu regularnego wychodzi ${\displaystyle n}$ krawędzi. Graf regularny stopnia ${\displaystyle n}$ określa się dla wygody mianem grafu ${\displaystyle n}$-regularnego. Szczególnym przypadkiem grafów regularnych są grafy kubiczne (grafy ${\displaystyle 3}$-regularne)^[1].

• 
  graf 0-regularny
• 
  graf 1-regularny
• 
  graf 2-regularny

Znane grafy i klasy grafów regularnych

• grafy kubiczne, żmirłacze
• grafy pełne
• grafy silnie regularne
• graf Petersena

Graf silnie regularny

Graf silnie regularny to graf regularny w którym wszystkie pary sąsiadujących ze sobą wierzchołków mają tyle samo wspólnych sąsiednich wierzchołków, i wszystkie pary niesąsiadujących ze sobą wierzchołków też mają tyle samo wspólnych wierzchołków sąsiednich.

Znane grafy i klasy grafów silnie regularnych

• graf Petersena