Graphe régulier

En théorie des graphes, un graphe régulier est un graphe où tous les sommets ont le même nombre de voisins, c'est-à-dire le même degré ou valence. Un graphe régulier dont les sommets sont de degré ${\displaystyle k}$ est appelé un graphe ${\displaystyle k}$-régulier ou graphe régulier de degré ${\displaystyle k}$.

Un graphe 0-régulier est un ensemble de sommets déconnectés; un graphe 1-régulier a un nombre pair de sommets et est un ensemble d'arêtes déconnectées ou couplage ; enfin, un graphe 2-régulier est un ensemble de cycles déconnectés. Un graphe 3-régulier est aussi appelé graphe cubique.

• 
  graphe 0-régulier
• 
  graphe 1-régulier
• 
  graphe 2-régulier
• 
  graphe de Petersen (graphe cubique particulier)
• 
  graphe infini 2-régulier

Un graphe fortement régulier est un graphe régulier où chaque paire de sommets adjacents a le même nombre ${\displaystyle l}$ de voisins en commun et où chaque paire de sommets non-adjacents a le même nombre ${\displaystyle n}$ de voisins en commun. Les plus petits graphes qui sont réguliers sans être fortement réguliers sont le graphe cycle et le graphe circulant, tous deux à 6 sommets. Le graphe complet ${\displaystyle K_{m}}$ est fortement régulier pour tout ${\displaystyle m}$

Une condition nécessaire et suffisante pour l'existence d'un graphe ${\displaystyle k}$-régulier à ${\displaystyle n}$ sommets est que ${\displaystyle nk}$ soit pair et que ${\displaystyle n\geq k+1}$^[1].

Un théorème de Crispin Nash-Williams affirme que tout graphe ${\displaystyle k}$-régulier ayant ${\displaystyle 2k+1}$ sommets admet un cycle hamiltonien^[2].

Soit ${\displaystyle A}$ la matrice d'adjacence du graphe. Le graphe est régulier si et seulement si ${\displaystyle {\begin{bmatrix}1\\\vdots \\1\end{bmatrix}}}$ est un vecteur propre de ${\displaystyle A}$. Lorsque c'est un vecteur propre, il correspond à une valeur propre qui est égale au degré du graphe.