Weekly Problem 41 - 2007
The Queen of Spades always lies for the whole day or tells the truth for the whole day. Which of these statements can she never say?
Now consider the five vertices around the lower horizontal
pentagon. Only one of these can be red because if two were red then
there would be a vertex with two red neighbours which is not
The argument shows that of the eleven vertices discussed only
two can be red. We know that there is a third red vertex so it must
be the vertex at the bottom. However if the bottom vertex is red
then there will be two vertices on the lower horizontal pentagon
having two red neighbours which is not allowed.
We have reached a contradiction.
So the assumption that no vertex has more than one red neighbour
We have proved that there is at least one vertex with two red