  Gallai's colouring theorem states that if the edges of a complete graph are
3-coloured, with each colour class forming a connected (spanning) subgraph,
then there is a triangle that has all 3 colours. What happens for more colours:
if we $k$-colour the edges of the complete graph, with each colour class
connected, how many of the $\binom{k}{3}$ triples of colours must appear as
triangles?
  In this note we show that the `obvious' conjecture, namely that there are
always at least $\binom{k-1}{2}$ triples, is not correct. We determine the
minimum asymptotically. This answers a question of Johnson. We also give some
results about the analogous problem for hypergraphs, and we make a conjecture
that we believe is the `right' generalisation of Gallai's theorem to
hypergraphs.
