Bonjour en maths expertes j’ai un dm à faire, voici la question:
Étude du problème
Colorier un graphe, c'est affecter une couleur à chaque
sommet, de sorte que deux sommets adjacents ne
portent pas la même couleur.
Le nombre chromatique, noté y, est le plus petit nombre
de couleurs nécessaires pour colorier un graphe.
Considérons un graphe G.
Un sous-graphe de G est un graphe G' composé de
certains sommets de G et de toutes les arêtes reliant ces
sommets.
Notons m l'ordre du plus grand des sous-graphes
complets de G et A le plus grand degré des sommets de
G. Alors m≤ y ≤A + 1.
Prouver cette inégalité.
f(x)