Problem 1067

We start by showing that for all $k \leqslant n^{2}-n$, there might not be two stations connected by both companies. Obviously, it is sufficient to provide an example for $k=n^{2}-n$. Suppose that $A$ connects stations $i$ and $i+1$ for all $1 \leqslant i \leqslant n^{2}$ with $n \nmid i$, and $B$ connects stations $i$ and $i+n$ for $1 \leqslant i \leqslant n^{2}-n$. It is easy to verify that no pair of stations is connected by both companies.

Now, let's show that for $k=n^{2}-n+1$, there must be a pair of stations that are connected by both companies. Suppose, for the sake of contradiction, that there exists a configuration where this is not the case.

Consider the different stations as graphs where two vertices are connected by a blue edge if company $A$ connects the two stations, and by a red edge if company $B$ connects them. By the conditions of the problem, the two resulting red and blue graphs are trees (in fact, they are even "chains"). Let $k$ be the number of connected components in the red graph. The graph then has $n^{2}-k$ edges, where $k=n-1$. The same applies to the blue graph. Moreover, by hypothesis, there are no two vertices in the same blue connected component that are in the same red connected component. Therefore, each blue connected component has at most $n-1$ vertices. Since the blue graph has $n-1$ connected components, this implies that there are at most $(n-1) \cdot (n-1) < n^{2}-n+1$ edges in total. We have the desired contradiction.