58th Ukrainian National Mathematical Olympiad

Let $A$ is a vertex with the smallest degree $k(A)$. If $k(A)<27$, then there exist at least 3 vertices that are not connected with a chosen vertex. Then 3 of those vertices together with $A$

make a not connected graph, so it contradicts the condition. Thus, the smallest size of graph is $\frac{1}{2}\cdot 27\cdot 30=405$. We want to show that such a graph exists. Call vertices $A_1,A_2,...,A_{29},A_{30}$ and $A_1=A_{31}$. Connect every vertex $A_i$ with 27 vertices, all except $A_{i-1}$ and $A_{i+1}$, $i=1,30$. We want to show that such graph satisfies the condition. Suppose by contradiction that, condition is not satisfied for vertices $A_i,A_j,A_k$ and $A_l$, where, $i<j<k<l$, moreover the biggest number of vertices is between $A_i$ and $A_l$. Then there are edges between $A_i\leftrightarrow A_k,A_i\leftrightarrow A_l$ and $A_j\leftrightarrow A_l$, since they are not neighbors. Obtained contradiction finishes the proof.