#### You may also like

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?

# Proximity

##### Stage: 4 Challenge Level:

Solution to Proximity by Tony and John, State College Area High School, PA, USA.
 We give a proof by contradiction. Suppose no vertex has more than one red neighbour. Without loss of generality say the vertex at the top is red. Then none of the five vertices around the upper horizontal pentagon, which are neighbours of the top vertex, are red. This is because if any of them were red then there would be two vertices each having two red neighbours which is not allowed.

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 allowed.

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.