# Proximity

##### Age 14 to 16 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.