, 2023

Answer: $n = 2024, 2026, 2028, 2696, 4044$.

Let us reformulate a more general version of the problem in terms of the graph theory: In a regular graph $G$ on $n$ vertices each vertex has a degree $k < n-1$ and if two vertices are not neighbours then they have exactly $k-1$ common neighbours. Find all pairs $(n, k)$ satisfying these conditions.

If $n = 2024$ then the complete graph satisfies the conditions. The answer in the remaining cases: all pairs $(n, k) = (2ab, 2a(b-1)+1)$ where $a > 1$ and $b$ are positive integers and also all pairs $(n, n-3)$ (if $n = 4b$ then all pairs $(n, n-3)$ are among pairs given by $(n, k) = (2ab, 2a(b-1)+1)$).

Let $w$ be a vertex with neighbours $v_1, \dots, v_k$. If some vertex is not a neighbour of $w$ then it is directly connected to $k-1$ neighbours of $w$ and hence it has exactly $1$ neighbour among remaining vertices. Therefore, all vertices in the graph $G - \{w, v_1, \dots, v_k\}$ have degree $1$ and consequently the number of vertices not directly connected to $w$ is even. Let us denote them by $u_1, \dots, u_{2l}$. Since $1 + l + 2l = n$ we get that $2l = n - k - 1$. Without loss of generality

for $1 \le t \le l$ let $u_{2t-1}$ and $u_{2t}$ be neighbours. When $l = 1$ we get a pair $(n, n-3)$. Let $l \ge 2$. For any $t \ge 3$ the vertices $u_1$ and $u_t$ are not neighbours and their unique neighbours among vertices $u_i$ are not common. Hence, $u_1$ and $u_t$ have $k-1$ neighbours among vertices $v_i$. The same is true for $u_2$ and $u_t$. Therefore, all these vertices are connected to the same $k-1$ vertices of $w$. Without loss of generality, let $v_1$ be the vertex not connected to $u_i$, $1 \le i \le 2l$. Since the degree of $v_1$ is $k$ it is directly connected to each $v_i$. Therefore, for each $2 \le i \le k$ the degree of $v_i$ in $G - \{w, v_1, u_1, \dots, u_{2l}\}$ is $k-1-1-2l = 2k-n-1$. Then the graph on the vertices $v_2, \dots, v_k$ satisfies problem conditions with new parameters $(k-1, 2k-n-1)$. Since $(k-1)-(2k-n-1) = n-k$, by repeating the same procedure we get that the graph $G$ contains pieces with $2l+2$ vertices and each piece contains $l+1$ perfectly matching edges and all possible edges between different pieces are drawn. By denoting $l+1$ by $a$ and the number of pieces by $b$ we get the desired answer.

When $k = 2023$ from $2a(b-1)+1 = 2023$ we get that $a|1011 = 3 \cdot 337$. Therefore the possible values for $a$ are $a = 3, 337, 1011$ and we get $n = 2ab = 2028, 2696, 4044$. The pair $(n, n-3)$ yields $n = 2026$.