Maths Olympiad Prep

Library / /11 of 19

Combinatorics Difficulty 5.4 AIME, harder Prove it Soviet Union

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

Solution:

Suppose not. We will obtain a contradiction.

Take any point AA. Suppose the four edges at AA are BABA, CACA, DADA, EAEA. If there is any other point XX not joined to any of AA, BB, CC, DD, EE then with AA it forms the required pair of points. Suppose the three other points joined to BB (apart from AA) are B1B_1, B2B_2, B3B_3. Similarly CiC_i, DiD_i and EiE_i. Then all 12 points BiB_i, CiC_i, DiD_i, EiE_i must be distinct from each other and from AA, BB, CC, DD, EE or there would be a point XX. Thus, in particular, AA is not part of a triangle. But AA was arbitrary, so the graph has no triangles. Hence there cannot be an edge BiBjB_iB_j (or CiCjC_iC_j, DiDjD_iD_j, EiEjE_iE_j).

We have 4 edges AXAX, 12 edges BXBX, CXCX etc, and 17×4/2=3417 \times 4 / 2 = 34 edges in all, so there must be 18 edges BiCjB_iC_j etc. Each gives a different cycle length 5 through AA (e.g. ABBiCjCABB_iC_jC). The same argument shows that every point must lie on 18 cycles length 5. Hence there must be a total of 17×18/517 \times 18 / 5 such cycles. Contradiction.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.