Graphes sans Pn induits - Collège Georges Pompidou (Cajarc) Lycée Raymond Savignac (Villefranche de Rouergue)

Après avoir introduit la notion de graphe, on définit celle de chemin induit. Un chemin induit de longueur n-1 sur un graphe est une succession de n sommets et n-1arêtes du graphe pour lequel il n'existe pas dans le graphe et entre les sommets de ce chemin d'autres arêtes que celles du chemin. Un tel chemin est noté Pn. La question est alors de caractériser les graphes qui sont sans Pn. Au jour d’aujourd’hui on ne connaît pas de caractérisation simple de tels graphes pour n quelconque. Par contre le problème est faisable pour des petites valeurs de n : n=2, n=3, n=4. C’est l’objet de cette recherche.