MAIS…
Considérons maintenant le sous-graphe obtenu en ôtant les sommets C et G et les arêtes ayant un de ces sommets pour extrémité.
Il est clair que le nombre chromatique de ce sous-graphe est 3.
A
B
F
E
H
D
Ainsi, en suivant l'algorithme de P-W, 4 couleurs sont nécessaires pour colorer le graphe de départ.
Pourtant le nombre chromatique de ce graphe est 3 comme le prouve le coloriage ci-contre
A
B
F
E
H
D
C
G