What can be the length of the shortest cycle in a graph where a single vertex is not connected to all others, any two non-adjacent vertices have a common neighbor, and if the number of vertices is denoted by $n$, then the sum of the squares of the degrees is $n^{2}-n ?$
Solution. Let the vertices of the graph be $A_{1}, A_{2}, \ldots, A_{n}$, and let the degree of $A_{i}$ be denoted by $a_{i}$. The set of vertices adjacent to $A_{i}$ is $\mathcal{B}_{i}$, and the set of vertices not adjacent to $A_{i}$ is $\mathcal{C}_{i}$. According to the problem's condition, every element of $\mathcal{C}_{i}$ has a neighbor in $\mathcal{B}_{i}$. Therefore, the sum of the degrees of the vertices in $\mathcal{B}_{i}$ is at least $\left|\mathcal{B}_{i}\right|+\left|\mathcal{C}_{i}\right|=n-1$. Summing these values from $i=1$ to $n$, we get at least $n(n-1)$. In this sum, each vertex appears as many times as its degree, so

$$
n^{2}-n=a_{1}^{2}+a_{2}^{2}+\ldots+a_{n}^{2} \geq n(n-1)
$$

Since equality holds here, equality must hold in all estimates, meaning that every vertex in $\mathcal{C}_{i}$ has exactly one neighbor in $\mathcal{B}_{i}$, and no two vertices in $\mathcal{B}_{i}$ are connected. This can also be stated as: no two neighbors of any vertex in the graph are connected. This implies that the graph does not contain a cycle of length 3. Therefore, it also cannot contain a cycle of length 4. If $A_{1}, A_{2}, A_{3}, A_{4}$ were the vertices of such a cycle in the order of their connections, then - since there is no cycle of length 3 - $A_{3} \in \mathcal{C}_{1}, A_{2}, A_{4} \in \mathcal{B}_{1}$, and $A_{3}$ would have two neighbors in $\mathcal{B}_{1}$: $A_{2}$ and $A_{4}$, which is a contradiction. Therefore, the length of the shortest cycle is at least 5. If the graph is a single cycle of length 5, then all conditions of the problem are satisfied; thus, the length of the shortest cycle can be 5. We will also show that the shortest cycle can never be longer than 5. In a shortest cycle $A_{1} A_{2}, \ldots, A_{k-1} A_{k}(k \geq 6)$, for example, the vertices $A_{1}$ and $A_{4}$, which are not connected, do not have a common neighbor; if $P$ were connected to both, then $A_{1} A_{2} A_{3} A_{4} P$ would be a cycle of length 5, which is a contradiction. Thus, the graph would not satisfy one of the problem's conditions.

Therefore, the length of the shortest cycle can only be 5.