Every node of an undirected connected graph is coloured white or black. Adjacent nodes can be compared and the outcome of each comparison is either 0 (same colour) or 1 (different colours). The aim is to discover a node of the majority colour, or to conclude that there is the same number of black and white nodes. We consider randomized algorithms for this task and establish upper and lower bounds on their expected running time. Our main contribution are lower bounds showing that some simple and natural algorithms for this problem cannot be improved in general.