Sous-graphe

Si $G$ est un graphe dont les sommets sont l'ensemble $S$ et les arêtes sont l'ensemble $A,$ et si $S'$ est une partie de $S,$ on appelle sous-graphe de $S$ formé à partir de $S'$ le graphe dont les sommets sont les éléments de $S'$ et les arêtes sont les éléments de $A$ reliant deux sommets de $S'.$ Par exemple, dans l'exemple suivant, on a tracé un graphe et son sous-graphe formé à partir des sommets $A,B,C,D$ :

Un sous-graphe est dit stable s'il ne comporte aucune arête. Colorier un graphe revient à chercher des sous-graphes stables dans un graphe.