66th Belarusian Mathematical Olympiad

Answer: 405.

(Solution by B. Serankou, A. Yuran.) Let $A$ be the vertex of the graph such that the number of outgoing edges from $A$ is less than 27. Hence there exist three vertices $B$, $C$, $D$ which are not connected with $A$. If we delete all vertices except for $A$, $B$, $C$, $D$ then the obtained graph is not connected. Therefore, each vertex of the graph has at least 27 outgoing edges, so the number of the edges in the graph is greater than or equal to $(27\cdot 30)/2=405$.

Consider the graph with 30 vertices: $A_1,A_2,\dots ,A_{30}$. We connect each vertex $A_i$ with all others except for the vertices $A_{i-1},A_{i+1}$, $i=1,2,\dots ,30$ (here we assume that $A_0=A_{30}$, $A_{31}=A_1$). This graph has exactly 405 edges and satisfies the problem condition. Indeed, suppose contrary to our claim that there exists a non-connected graph with the vertices $A_a,A_b,A_c,A_d$, $0<a<b<c<d<31$. It is evident that the vertices $A_a$ and $A_c$ are adjacent since $|c-a|>1$ and $c<30$. Similarly, $A_b$ and $A_d$ are adjacent since $|d-b|>1$ and $b>1$. If $A_a$ and $A_d$ are not adjacent, then there is only one possibility: $a=1$ and $d=30$ since $d>a+1$. If $A_a$ and $A_b$ are not adjacent, then $b=2$ since $a<b<30$. If $A_b$ and $A_c$ are not adjacent, then $c=3$ since $b<c<31$. Then $A_c=A_3$ and $A_d=A_{30}$ are adjacent; therefore the graph with the vertices $A_a,A_b,A_c,A_d$ is connected, a contradiction. Thus, 405 is the smallest number of the edges of the graph satisfying the problem condition.