’ conjecture has not yet been settled in general, and its resolution is known to be a very difficult proplem. There is a related conjecture duc to Hadwiger (1943): IF g IS k-chromatic, then G is ‘contractible’ to a graph which contains . Wagner (1964) has shown that the case k =5 of Hadwiger’s conjecture is equivalent to the famous four-colour conjecture, to be discussed in chapter 9.