Romania — NMO Selection Tests for the Balkan and International Mathematical Olympiads

Letting $N(h, p) = (h-1) \cdot \min(p, h/2+1)$, we now proceed to prove by induction on $h$ that if the number of edges of a graph on $hp$ vertices does not exceed $N(h, p)$, then the graph is $h$-partite on $p$-element classes. The base case $h=1$ is clear.

Next, let $h \ge 2$ and let $G = (V, E)$ be a graph on $hp$ vertices which has at most $N(h, p)$ edges. If necessary, add some extra edges to obtain $|E| = N(h, p)$.

Begin by forming a $p$-element house $V_0$ of independent vertices $v_1, \dots, v_p$ by the following $p$-step greedy algorithm: Start with the empty set, and at step $j$ choose a vertex $v_j$ of maximal degree from the set of vertices joined by an edge to no $v_i$, $i < j$, and different from any of these; this set is nonempty, for if each of the remaining $hp-j+1$ vertices were joined by an edge to some $v_i$, $i < j$, then $|E| \ge hp-j+1 \ge hp-p+1 > N(h, p)$ — a contradiction. Notice that $\deg v_1 \ge \deg v_2 \ge \dots \ge \deg v_p$.

Let $d = \sum_{v \in V_0} \deg v$, so the subgraph $G'$ induced by the $p(h-1)$ vertices in $V \setminus V_0$ has exactly $N(h, p) - d$ edges. If $d \ge \Delta N = N(h, p) - N(h-1, p)$, then $G'$ is $(h-1)$-partite on $p$-element classes by the induction hypothesis, and the conclusion follows.

Henceforth, assume
$$d < \Delta N = \begin{cases} p, & \text{if } h \ge 2p-1, \\ h, & \text{if } h \le 2p-2, \end{cases} \quad (*)$$
and notice that $\Delta N \le h$ in either case, so $d \le h-1$. Let $V'$ be the set of all vertices in $V \setminus V_0$ joined by an edge to some vertex in $V_0$, and notice that $|V'| \le d \le h-1$, and $\deg v \le \deg v_p$ for all vertices $v$ outside $V_0 \cup V'$.

If $\deg v_p = 0$, then the vertices outside $V_0 \cup V'$ are all isolated. Since $|V'| \le d \le h-1$, each vertex of $V'$ may be included in a different $p$-element house (other than $V_0$) along with $p-1$ vertices outside $V_0 \cup V'$ each, to obtain $|V'|$ more $p$-element houses. The remaining vertices, if any, are then arbitrarily split into $p$-element houses.

Finally, we rule out the case $\deg v_p \ge 1$. Suppose, if possible, that $\deg v_p \ge 1$. Then $\deg v_i \ge 1$, $i = 1, \dots, p$, and $d \ge p$, so (*) yields $\Delta N = h$, $h \le 2p-2$, and $N(h,p) = (h-1)(h+2)/2$. Hence $p \le d \le h-1 \le 2p-3$. The inequality $d \le 2p-3$ forces $\deg v_p = 1$, so $\deg v \le 1$ for all vertices $v$ outside $V_0 \cup V'$, and
$$\sum_{v \in V \setminus (V_0 \cup V')} \deg v \le hp - |V_0| = p(h-1).$$
Further on, split $V' = V_1 \cup \cdots \cup V_p$, where $V_j$ is the set of all vertices joined by an edge to $v_j$, but to no $v_i$, $i < j$. Notice that $|V_i| \le \deg v_i$, and $\deg v \le \deg v_i$ for all vertices $v$ in $V_i$. Consequently,
$$\begin{aligned} \sum_{v \in V_0 \cup V'} \deg v &= \sum_{i=1}^{p} \left( \deg v_i + \sum_{v \in V_i} \deg v \right) \le \sum_{i=1}^{p} \deg v_i (\deg v_i + 1) \\ &= \sum_{i=1}^{p} (\deg v_i - 1)^2 + 3d - p. \end{aligned}$$
Since $\deg v_i \ge 1$, $i = 1, \dots, p$,
$$\sum_{i=1}^{p} (\deg v_i - 1)^2 \le \left( \sum_{i=1}^{p} (\deg v_i - 1) \right)^2 = (d-p)^2,$$
so (recalling that $d \le h-1$)
$$\begin{aligned} \sum_{v \in V_0 \cup V'} \deg v &\le (d-p)^2 + 3d - p \le (h-p-1)^2 + 3(h-1) - p \\ &= (h-1)(h+2) + p(p-2h+1) = 2N(h,p) + p(p-2h+1). \end{aligned}$$
Hence, by the preceding,
$$\begin{aligned} 2N(h,p) = 2|E| &= \sum_{v \in V} \deg v = \sum_{v \in V_0 \cup V'} \deg v + \sum_{v \in V \setminus (V_0 \cup V')} \deg v \\ &\le 2N(h,p) + p(p-2h+1) + p(h-1) = 2N(h,p) + p(p-h) \\ &< 2N(h,p), \end{aligned}$$
which is a contradiction. This ends the proof.