Problem 2049

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.