Problem:
A graph has 17 points and each point has 4 edges. Show that there are two points which are not joined and which are not both joined to the same point.
Problem:
A graph has 17 points and each point has 4 edges. Show that there are two points which are not joined and which are not both joined to the same point.
Solution:
Suppose not. We will obtain a contradiction.
Take any point . Suppose the four edges at are , , , . If there is any other point not joined to any of , , , , then with it forms the required pair of points. Suppose the three other points joined to (apart from ) are , , . Similarly , and . Then all 12 points , , , must be distinct from each other and from , , , , or there would be a point . Thus, in particular, is not part of a triangle. But was arbitrary, so the graph has no triangles. Hence there cannot be an edge (or , , ).
We have 4 edges , 12 edges , etc, and edges in all, so there must be 18 edges etc. Each gives a different cycle length 5 through (e.g. ). The same argument shows that every point must lie on 18 cycles length 5. Hence there must be a total of such cycles. Contradiction.