Maths Olympiad Prep

Library / /35 of 42

Combinatorics Difficulty 6.7 National olympiad Prove it Ireland

There are 28 towns on the island of Mathematia. Each pair of towns is either connected by a single road, or is not connected. It turns out that for any two towns AA and BB that have the same number of roads connected to them, there is no road that connects AA to BB. Determine, with proof, the maximum number of roads on the island of Mathematia.

Solution

The problem can be restated as follows: Given a graph on 28 vertices, where no two vertices of the same degree ii are connected by an edge (1i271 \le i \le 27), determine (with proof) the maximum number of edges in the graph.
For 0i270 \le i \le 27, let aia_i denote the number of vertices of degree ii. Thus the total number of edges in the graph is
Ne=0×a0+1×a1++27×a272=(a27)+(a27+a26)+(a27+a26+a25)++(a27+a26++a1)2. N_e = \frac{0 \times a_0 + 1 \times a_1 + \cdots + 27 \times a_{27}}{2} = \frac{(a_{27}) + (a_{27} + a_{26}) + (a_{27} + a_{26} + a_{25}) + \cdots + (a_{27} + a_{26} + \cdots + a_1)}{2}.
Now, consider any vertex vv of degree ii. None of its ii neighbouring vertices can have degree ii, so we have ai28ia_i \le 28 - i. In particular a271a_{27} \le 1, a27+a261+2a_{27} + a_{26} \le 1 + 2, and so on, up until a27++a211+2++7a_{27} + \cdots + a_{21} \le 1 + 2 + \cdots + 7. Also, for each i20i \le 20 we have a27++ai28a_{27} + \cdots + a_i \le 28, since the sum cannot be larger than the total number of vertices in the graph. This yields the following upper bound on the number of edges:
Ne(1)+(1+2)+(1+2+3)++(1+2++7)+20×282=322. N_e \le \frac{(1) + (1+2) + (1+2+3) + \cdots + (1+2+\cdots+7) + 20 \times 28}{2} = 322.
This upper bound is attained by the following graph: Partition the 28 vertices into 7 groups of size 1, 2, ..., 7, respectively. Any pair of vertices is connected by an edge if and only if the two vertices lie in different groups. It is easy to see that this graph satisfies the condition of the problem. Because each vertex in the group of size ii has degree 28i28 - i, the total number of edges in this graph is
Ne=12i=17i(28i)=14i=17i12i=17i2=39270=322, N_e = \frac{1}{2} \sum_{i=1}^{7} i(28 - i) = 14 \sum_{i=1}^{7} i - \frac{1}{2} \sum_{i=1}^{7} i^2 = 392 - 70 = 322,
as required.

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 and solution reproduced as published; topic and difficulty added by this site.