Turkish Mathematical Olympiad

The answer is: $k=2n-3$. If all pairs of cities are directly connected (complete graph) then all roads from $A$ and all roads to $B$ must be oriented: $k\ge (n-1)+(n-1)-1=2n-3$ or if $\mathrm{deg}(A)=\mathrm{deg}(B)=n-1$, all other vertices have degree $2$, then again we have to orient all $2(n-2)+1=2n-3$ roads. Now we prove that by orienting of at most $2n-3$ roads the existence of a required road for any fixed road $L$ can be guaranteed. We say that a path containing not oriented roads $A_1{A}_2,A_2{A}_3,\dots ,A_{l-1}{A}_l$ is minimal, if there is no road $A_l{A}_j$ with $1\le i,j\le l,|i-j|\ne 1$. At the first stage we orient all roads belonging to the minimal path ${\Gamma }_1$ without self-intersections starting at $A$ and ending at $B$: ${\Gamma }_1=\{A_1{A}_2,A_2{A}_3,\dots ,A_{l-1}{A}_l\}$, where $A=A_1,A_l=B$. If ${\Gamma }_1$ includes all cities, then we are done. At the second stage we orient all roads of a minimal path ${\Gamma }_2$ starting at some city $B_1=A_{p_1}\in {\Gamma }_1$ and ending at some city $B_m=A_{p_m}\in {\Gamma }_1$ and including new cities $B_2,B_3,\dots ,B_{m-1}$ not lying on ${\Gamma }_1$. Such a path exists since our graph is 2-connected: there is a path between any two cities even after the elimination of any given road. We say that a path $B_1{B}_2,B_2{B}_3,\dots ,B_{m-1}{B}_m$ is stretched, if there is no road $A_i{B}_j$ with $1\le i\le p_1-1$ or $p_2+1\le i\le l$ and $2\le j\le m-1$. In other words, ${\Gamma }_2$ is stretched means that $B_1$ is closer to $A$ than any other city inside ${\Gamma }_2$ and $B_m$ is closer to $B$ than any other city inside ${\Gamma }_2$. If ${\Gamma }_1$ and ${\Gamma }_2$ contain all cities we are done. If not, at the third stage we orient all roads of some minimal and stretched path ${\Gamma }_3$, starting at some city on ${\Gamma }_1\cup {\Gamma }_2$ and ending at some city lying on ${\Gamma }_1\cup {\Gamma }_2$, including new cities. After $q$ steps $\Gamma ={\cup }_{i=1}^q{\Gamma }_i$ will contain all cities. Now any road $l$ either belongs to some ${\Gamma }_i$ or connects ${\Gamma }_i$ to ${\Gamma }_j$. If $l$ belongs to some ${\Gamma }_i$, it is already oriented and there is a path starting at $A$ passing through $l$ and ending at $B$. Indeed, let $l\in {\Gamma }_s$. This path has two parts, first part connecting $A$ with $l$ and the second part, connecting $l$ with $B$. In order to get the first part, we take an edge $l$ and go back through oriented edges ${\Gamma }_s$ till the first edge of ${\Gamma }_s$, then we go back through oriented edges of some other ${\Gamma }_i$ having intersection with ${\Gamma }_s$ ($i$ is not necessarily equal to $s-1$), and so on until getting $A$. In order to get the second part, we take an edge $l$ and go through oriented edges ${\Gamma }_s$ till the first edge of ${\Gamma }_s$, then we go through oriented edges of some other ${\Gamma }_i$ having intersection with ${\Gamma }_s$ ($i$ is not necessarily equal to $s+1$), and so on until getting $B$. This paths pass only through roads oriented at stages 1, 2, ..., $q$. Now suppose that $l$ does not belong to ${\cup }_{i=1}^q{\Gamma }_i$ and somehow oriented, say it connects a city $C\in {\Gamma }_i$ and $D\in {\Gamma }_j$. Then the required path again has two parts, first part connecting $A$ with $C$ and the second part connecting $D$ with $B$. We get these parts as in the first case. It can be readily checked that since constructed paths ${\Gamma }_1,\dots ,{\Gamma }_q$ are minimal and stretched, the required path is correctly defined. Now we note that the total number of roads oriented at stages 1, 2, ..., $q$ is at most $2n-3$. Indeed, suppose that at some stage we draw a path ${\Gamma }_i$ including $l$ new cities. Then the number of oriented roads is $l+1$. Thus, the total number of oriented roads is maximal if ${\Gamma }_1$ includes one road and each other ${\Gamma }_i$ included two roads as in the second example constructed above. In this case the total number of oriented roads is $2n-3$. Done.