IRL_ABooklet

The problem can be restated as follows: Given a graph on 28 vertices, where no two vertices of the same degree $i$ are connected by an edge ($1\le i\le 27$), determine (with proof) the maximum number of edges in the graph. For $0\le i\le 27$, let $a_i$ denote the number of vertices of degree $i$. Thus the total number of edges in the graph is $$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 $v$ of degree $i$. None of its $i$ neighbouring vertices can have degree $i$, so we have $a_i\le 28-i$. In particular $a_{27}\le 1$, $a_{27}+a_{26}\le 1+2$, and so on, up until $a_{27}+\cdots +a_{21}\le 1+2+\cdots +7$. Also, for each $i\le 20$ we have $a_{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: $$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 $i$ has degree $28-i$, the total number of edges in this graph is $$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.