Graphe régulier
Définition : 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 {a1,...,ap},
d'autre part {ap+1,...,a2p}. Les arêtes sont les suivantes :
- a1 est relié à ap+1, ap+2 et ap+3;
- a2 est relié à ap+2, ap+3 et ap+4;
- ...
- ap-2 est reliés à a2p-2, a2p-1 et a2p;
- ap-1 est relié à a2p-1, a2p et a1;
- ap est relié à a2p, a1 et a2.