Démonstration sur les graphe

[chtirico]

Bonjour,

J'ai une démonstration à faire sur les graphes mais je n'ai aucune idée. pourriez vous m aider. merci d'avance

Je note NC(G) le nombre chromatique de G
Je dois prouver que dans un graphe G, il existe au moins NC(G) sommets de degré supérieur ou égal à NC(G) - 1

[Ben314]

Salut,
Perso, je raisonerais par contraposition :
On fixe un entier c et on suppose que le graphe G contient nAvec cette hypothèse, si tu montre qu'on peut le colorier avec strictement moins de c couleurs, cela prouve que NC(G)