Un arbre à n arêtes est gracieux si l'on peut étiqueter ses sommets de 0 à n sans doublon, ses arêtes de 1 à n sans doublon, et de telle sorte que la valeur d'une arête soit la différence (en valeur absolue) des valeurs des sommets situés à ses extrémités.
Une conjecture encore ouverte aujourd'hui est que tout arbre est gracieux. Ici, les élèves explorent la validité de cette conjecture sur les étoiles, les chemins et les chenilles, où des algorithmes de coloration gracieuse sont exhibés. Le cas des homards et des araignées est également considéré, mais aucun algorithme générique n'est proposé pour ces familles de graphes.
Une conjecture encore ouverte aujourd'hui est que tout arbre est gracieux. Ici, les élèves explorent la validité de cette conjecture sur les étoiles, les chemins et les chenilles, où des algorithmes de coloration gracieuse sont exhibés. Le cas des homards et des araignées est également considéré, mais aucun algorithme générique n'est proposé pour ces familles de graphes.