Graphes connexes non isomorphes et k-réguliers - Collège Georges Pompidou (Cajarc) Lycée Raymond Savignac (Villefranche de Rouergue)

Après avoir introduit la notion de graphe connexe, on définit celle d’isomorphisme et de k-régulier. Deux graphes sont isomorphes si on peut passer de l’un à l’autre en renumérotant les sommets. Un graphe est k-régulier si tous ses sommets sont de degré k. Rappelons que le degré d’un sommet est le nombre d’arêtes adjacentes à ce sommet. Il n’existe pas de formule générale qui donne le nombre de graphes connexes non isomorphes et k-régulier mais on peut résoudre le problème pour des petites valeurs de k ou des petites valeurs de n. C’est l’objet de cette recherche.