SELECTION TESTS OF THE BELARUSIAN TEAM TO THE IMO

Let's translate the problem into the language of graphs.

Given a bipartite graph $G$ with parts $A$ and $B$ having the same number of vertices: $|V(A)|=|V(B)|=k$. The degree of each vertex in $B$ is $n$. For any two vertices $u,v$ of the part $A$, there are exactly two vertices in $B$ that are adjacent to both vertices $u$ and $v$.

a) Prove that the degree of any vertex in $A$ is also equal to $n$.

b) Prove that there is a simple path in the graph that contains at least $\lfloor \frac{(n+1{)}^2}{4}\rfloor$ vertices in each part.

First, let's prove that $k=\left(\genfrac{}{}{0ex}{}{n}{2}\right)+1$ and that the degree of each vertex in $A$ is equal to $n$.

Let's count the number of pairs ($\{a,a^{\prime }\},b$) where $a\ne a^{\prime }$, $a,a^{\prime }\in V(A)$, $b\in V(B)$ and $b$ is adjacent to $a$ and $a^{\prime }$. On the one hand, we have $|V(B)|$ ways to select $b$ and each such vertex gives $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ pairs $a,a^{\prime }$ to which it is adjacent. On the other hand, there are $\left(\genfrac{}{}{0ex}{}{|V(A)|}{2}\right)$ ways to select distinct $a$ and $a^{\prime }$, and further, for each pair, there are exactly two ways to select $b$, according to the second property of our graph. Thus, $\left(\genfrac{}{}{0ex}{}{n}{2}\right)k=2\left(\genfrac{}{}{0ex}{}{k}{2}\right)$, which implies that $k=\left(\genfrac{}{}{0ex}{}{n}{2}\right)+1$.

Let's take an arbitrary vertex $a$ from $A$ and let it have degree $d$. Let us count in two ways the number of pairs $(a^{\prime },b)$ where $a^{\prime }\in V(A)$, $b\in V(B)$, $a^{\prime }\ne a$ and vertex $b$ is adjacent to both vertices $a$ and $a^{\prime }$. On the one hand, we have $|V(A)|-1$ options to choose a vertex $a^{\prime }$ and for each such vertex we have exactly two choices of a vertex $b$. On the other hand, each of the $d$ neighbors of a vertex $a$ has degree exactly $n$, which gives $(n-1)d$ pairs in question (the neighbors of a given vertex from $V(B)$ must be different from $a$, so there are $n-1$ of them). Thus $(n-1)d=2(k-1)=2\left(\genfrac{}{}{0ex}{}{n}{2}\right)$, which means that $d=n$.

Now let's move on to finding a path. Since the graph is regular, then by Hall's theorem there is a perfect matching in it – a set of $k$ pairwise non-adjacent edges. Let $I$ be such a matching. Let us take the longest such path $P=b_1{a}_1,\dots ,b_r{a}_r$, where $b_1\in V(B)$ and $a_r\in V(A)$, with the following property:

if a vertex $x$ is in $P$, then the vertex $y$ adjacent to $x$ in the matching $I$ is also in $P$.

(Note that this condition does not require that edges from $I$ also be in our simple path.) Then all neighbors of the ends of $P$ lie in $P$. In fact, if one of the ends of $P$ has a neighbor outside $P$, then the neighbor of this vertex in $I$ is also not in our path and then we can extend our path by two vertices so that it starts and ends at different shares.

Let now $b_i$ ($1\le i\le r$) be one of the neighbors of a vertex $a_k$ in path $P$. Then the path $$b_1{a}_1\dots b_i{a}_r{b}_r{a}_{r-1}\dots a_i$$ also has the above property. In particular, all neighbors of the vertex $a_i\in V(A)$ also lie in $P$. Since $a_r$ has $n$ neighbors, we have a minimum of $n$ vertices $a_{i_1},\dots ,a_{i_n}$ from $A$ each of which has neighbors only in the path $P$. Since vertices $a_{i_1}$ and $a_{i_2}$ have exactly two neighbors in common, they have a total of $n+(n-2)$ neighbors in $P$. Next, consider the vertex $a_{i_3}$ – it has two common neighbors with each of the previous vertices, that is, a maximum of 4 common neighbors have already been counted. This gives $n-4$ new neighbors different from the previous ones. Reasoning in this way, we get $$r\ge n+(n-2)+(n-4)+\cdots =\lfloor \frac{(n+1{)}^2}{4}\rfloor ,$$ which is what was required.