Graphe régulier
Un graphe est dit régulier s'il est simple, et si tous ses sommets ont le même degré, c'est-à-dire si de chaque sommet il part le même nombre d'arêtes.
Il n'existe pas toujours de graphe régulier dont le degré de chaque sommet est fixé à l'avance. Par exemple, si on s'intéresse aux graphes réguliers de degré 3, c'est-à-dire que chaque sommet est de degré 3, alors, il est facile de prouver que le nombre de sommets doit être supérieur ou égal à 4, et qu'il doit être un nombre pair. Réciproquement, on peut toujours construire un graphe régulier de degré 3 de cardinal $2p,$ avec $p>1.$ Pour $p=2,$ on considère le graphe complet à 4 sommets. Pour $p>2,$ on procède comme suit. On partage l'ensemble des sommets en 2, d'une part $\{a_1,\dots,a_p\},$ d'autre part $\{a_p+1,\dots,a_2p\}.$ Les arêtes sont les suivantes :
- $a_1$ est relié à $a_{p+1},$ $a_{p+2}$ et $a_{p+3};$
- $a_2$ est relié à $a_{p+2},$ $a_{p+3}$ et $a_{p+4};$
- $\dots$
- $a_{p-2}$ est reliés à $a_{2p-2},$ $a_{2p-1}$ et $a_{2p};$
- $a_{p-1}$ est relié à $a_{2p-1},$ $a_{2p}$ et $a_1;$
- $a_p$ est relié à $a_{2p},$ $a_1$ et $a_2.$