Hadwigerova domněnka

Dosud nedokázané tvrzení (1943): každý souvislý graf s chromatickým číslem n se dá postupnými kontrakcemi převést na úplný graf s n uzly. Kontrakcí přitom rozumíme splynutí dvou uzlů, které byly původně spojeny hranou. Pro n = 5 je Hadwigerova domněnka ekvivalentní s problémem čtyř barev.