MAIS…
H
F
E
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é. |
D
A
B
| Il est clair que le |
nombre chromatique de
| ce sous-graphe est 3. |
G
H
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 |
F
E
A
D
B
C