Balkan Mathematical Olympiad Shortlisted Problems

Use the obvious graph interpretation. We show that any such graph is one of the following: the full graph $K_n$, the circular graph $C_n$, and for $n$ even, the bipartite graph $K_{\frac{n}{2},\frac{n}{2}}$. First, we show that these graphs satisfy the condition. For $K_n$, we can choose any long path and the short path is the edge. For $C_n$, we have exactly two paths between any two vertices, and one of them has at most as many vertices as the other. * For $K_{\frac{n}{2},\frac{n}{2}}$, if the vertices are on different sides, the short path is the edge. Otherwise, take any long path. We observe that it alternates between the sides and begins and ends on one side. Therefore, there is a vertex on the other side that doesn't appear in the long path. Additionally, there is a short path that passes through this vertex. Next, we show that only these graphs work for $n$ large enough. The graph is clearly connected, as any two vertices belong to a path. Consider a longest path in the graph. Let $p$ be its length and denote the vertices in the path by $V_1,V_2,\dots ,V_p$ in the corresponding order. We can assume that this path is the long path between $V_1$ and $V_p$ that has a corresponding short path through other vertices. We show that the edge $V_1{V}_p$ belongs to the graph. If the edge doesn't exist, the short path has length at least two, implying that there is a vertex $X$ different from $V_i,i\in \{1,\dots ,p\}$ such that there exists an edge from $V_1$ to $X$. Then the path $X{V}_1{V}_2\dots V_p$ has length $p+1$, which gives a contradiction. Next we show that $p=n$, i.e. that the cycle $V_1\dots V_p$ contains all the vertices. If there exists another vertex $A$ connected with an edge to a vertex $V_i$, then the path $A{V}_i{V}_{i+1}\dots V_{i-1}$ has length $p+1$, which gives a contradiction. Since the graph is connected, the cycle contains all vertices. For two vertices of the graph, we say that they have distance $r$ if there are exactly $r-1$ vertices between them on a side of the cycle. Observe that they also have distance $n-r$. If we relabel the vertices by $A_1,A_2,\dots ,A_n$ in such a way that we know the graph has $n-1$ of the edges $A_i{A}_{i+1},i\in \{1,\dots ,n\}$ (where $A_{n+1}=A_1$), then it also has the last one. This is shown same as before. Next, we show that if we have an edge between $V_i$ and $V_j$, then we also have an edge between $V_{i+1}$ and $V_{j+1}$. Assume $i<j$. Consider the path $$V_{i+1}{V}_{i+2}\dots V_j{V}_i{V}_{i-1}\dots V_{j+1}$$

of length $n$. As before, we conclude that there is an edge between $V_{i+1}$ and $V_{j+1}$. Repeating this, we get that if we have an edge between two vertices at distance $r$, then we have edges between any two vertices at distance $r$. Define $S$ as the set of numbers $1\le r\le n-1$ such that the graph has the edges of distance $r$. Note that $1,n-1\in S$. For positive integers $a$ and $b$ with $a+b\le n-1$, consider the ordering $$V_1,V_{a+b},V_{a+b-1},\dots ,V_{a+1},V_{a+b+1},V_{a+b+2},\dots ,V_n,V_a,V_{a-1},\dots ,V_1.$$ The distance between two consecutive vertices in this ordering is $1,a,b$ or $a+b-1$. This implies that if two numbers from the multiset $\{a,b,a+b-1\}$ belong to $S$, so does the third one. Now, if $2\in S$, we take $b=2$ and easily get that $S$ contains any number from $1$ to $n-1$. This gives us the solution $K_n$. Assume now $2\notin S$. This implies that we do not have two consecutive numbers smaller than $n-2$ in $S$. But as $2\notin S$, we also have $n-2\notin S$, so $S$ doesn't contain two consecutive integers. If $S=\{1,n-1\}$, we get the solution $C_n$. Otherwise, there exists $t\in S$ such that $3\le t\le n-3$. Consider the path $$V_t{V}_{t-1}\dots V_2{V}_{t+2}{V}_{t+1}{V}_1{V}_n\dots V_{t+3}$$ of length $n$.

Same as before, we get that there is an edge between $V_t$ and $V_{t+3}$. Therefore, we have $3\in S$. Now, taking $b=3$, we get that any odd number smaller than or equal to $n-1$ lies in $S$. Since we assumed $S$ doesn't contain consecutive integers, we get that $n$ is even and $S=\{1\le i\le n-1\mid i\text{ odd}\}$. This gives us the solution $K_{\frac{n}{2},\frac{n}{2}}$. Finally, the number of edges can be $n$, $\frac{n(n-1)}{2}$, and if $n$ is even it can also be $\frac{n^2}{4}$.