Olympiadium wrote: For a positive integer $n$, there are two countries $A$ and $B$ with $n$ airports each and $n^2-2n+ 2$ airlines operating between the two countries. Only one airline operates between each airport in $A$ and each airport in $B$, and that airline operates in both directions. Also, there are no flights between two airports in the same country. For two different airports $P$ and $Q$, denote by "$(P, Q)$-travel route" the list of airports $T_0, T_1, \ldots, T_s$ satisfying the following conditions. $T_0=P,\ T_s=Q$ $T_0, T_1, \ldots, T_s$ are all distinct. There exists an airline that operates between the airports $T_i$ and $T_{i+1}$ for all $i = 0, 1, \ldots, s-1$. Suppose that each airline operates at least one flight. Prove that there exist two airports $P, Q$ such that there is no or exactly one $(P, Q)$-travel route. It looks promising, but I suppose, there is a problem with the translation, or something. As stated we can consider a full bipartite graph on $(n,n)$ vertices with $n^2$ edges. Every company operates on only one edge, except one, that operates on all the rest. Obviously, for any two vertices there are more than one path that connects them. So, suppose the translation is wrong, and instead of companies we should think of edges, that is, for a bipartite graph $G(A,B)$ with $|A|=|B|=n$ and $|E|=n^2-2n+2$ we should prove some two vertices are either disconnected or there is only one path that connects them. This is again false. Consider a $2n$ cycle. This can be viewed as a bipartite graph, and obviously there are two paths between any two vertices. Since $2n\le n^2-2n+2$ when $n\ge 4$, we can add some edges and satisfy the statement condition.

dgrozev wrote: Olympiadium wrote: For a positive integer $n$, there are two countries $A$ and $B$ with $n$ airports each and $n^2-2n+ 2$ airlines operating between the two countries. Only one airline operates between each airport in $A$ and each airport in $B$, and that airline operates in both directions. Also, there are no flights between two airports in the same country. For two different airports $P$ and $Q$, denote by "$(P, Q)$-travel route" the list of airports $T_0, T_1, \ldots, T_s$ satisfying the following conditions. $T_0=P,\ T_s=Q$ $T_0, T_1, \ldots, T_s$ are all distinct. There exists an airline that operates between the airports $T_i$ and $T_{i+1}$ for all $i = 0, 1, \ldots, s-1$. Suppose that each airline operates at least one flight. Prove that there exist two airports $P, Q$ such that there is no or exactly one $(P, Q)$-travel route. It looks promising, but I suppose, there is a problem with the translation, or something. As stated we can consider a full bipartite graph on $(n,n)$ vertices with $n^2$ edges. Every company operates on only one edge, except one, that operates on all the rest. Obviously, for any two vertices there are more than one path that connects them. So, suppose the translation is wrong, and instead of companies we should think of edges, that is, for a bipartite graph $G(A,B)$ with $|A|=|B|=n$ and $|E|=n^2-2n+2$ we should prove some two vertices are either disconnected or there is only one path that connects them. This is again false. Consider a $2n$ cycle. This can be viewed as a bipartite graph, and obviously there are two paths between any two vertices. Since $2n\le n^2-2n+2$ when $n\ge 4$, we can add some edges and satisfy the statement condition. I think there are no mistakes in translation. But it seems to be very confusing, so I'll translate original statement in graph theorical language. The problem is like this. "There are two sets of vertices $A$, $B$ such that $|A|=|B|=n$. Each vertices in $A$ and $B$ is connected by an edge, and there are no edges in each $A$ and $B$(in other worlds, $G(A, B)$ is bipartite graph with $n^2$ edges as you mentioned above.). Suppose there are $n^2-2n+2$ colors, and each edges are colored in one of these colors. We define $(P, Q)-path$ like this; if there is path from vertice $P$ to $Q$ such that all of edges in this path are same color, and all of vertices in this path are different($P$ and $Q$ can be the vertices both in $A$ or $B$, or one is in $A$, and the other is in $B$.). Suppose that each $n^2-2n+2$ color has at least one edge colored in that color. Prove that there are two vertice $P$, $Q$ such that number of $(P, Q)-path$ is 0 or 1." Sorry for my bad english if you had trouble reading this...

dgrozev wrote: It looks promising, but I suppose, there is a problem with the translation, or something. As stated we can consider a full bipartite graph on $(n,n)$ vertices with $n^2$ edges. Every company operates on only one edge, except one, that operates on all the rest. Obviously, for any two vertices there are more than one path that connects them. So, suppose the translation is wrong, and instead of companies we should think of edges, that is, for a bipartite graph $G(A,B)$ with $|A|=|B|=n$ and $|E|=n^2-2n+2$ we should prove some two vertices are either disconnected or there is only one path that connects them. This is again false. Consider a $2n$ cycle. This can be viewed as a bipartite graph, and obviously there are two paths between any two vertices. Since $2n\le n^2-2n+2$ when $n\ge 4$, we can add some edges and satisfy the statement condition. Sorry if my translation was confusing As scnwust posted, it is about a path in complete bipartite graph $G(A, B)$ with $\vert A \vert = \vert B \vert = n$, and $n^2-2n+2$ colors. So $\vert E \vert = n^2$. By using the word airlines, I was meaning the airplane company. So one airline can operate more than one flight but should operate at least one flight. Each edge is colored with one of $n^2-2n+2$ colors and $(P, Q)$-travel route is a path with all of the edges colored the same. I added the graph theoretical wording:

Let $G_i=(V_i, E_i)$ be the graph of $i$th airline. If $G_i$ is disconnected, we can consider each components as different airlines. So I would change the statements that there are $m\geq n^2-2n+2$ airlines and each of them forms a connected graph. Denote the $i$th airline "good" if $|E_i|\geq2$. Let $t$ be the number of good airlines. Since each airline operates at least one flight, $1\leq t\leq n^2-m$. (The case $m=n^2$ is trivial, so assume $m<n^2$) Now we would count $N$, the number of airports pair $(P, Q)$ such that there exists a $(P, Q)$-travel route with a good airline. Without loss of generality, let good airlines be $1, 2, \cdots, t$. Since $G_i$ is connected, $v_i=|V_i|\leq |E_i|+1=e_i+1$. By double counting, $N\leq \sum_{i=1}^t{v_i \choose 2}\leq \sum_{i=1}^t {{e_i+1}\choose{2}}$. Also, $\sum_{i=1}^t e_i =n^2-m+t$, $e_i \geq 2$ for all $1\leq i\leq t$. Because of the concavity, $\sum_{i=1}^t {{e_i+1}\choose{2}}\leq (t-1){3\choose2}+{{n^2-m-t+3}\choose{2}}$. RHS is a quadratic function with axis $t=n^2-m-\frac{1}{2}$, so it is the maximum when $t=1$. Hence, $N\leq {{n^2-m+2}\choose{2}}\leq {{2n}\choose{2}}$. If the equality holds, $m=n^2-2n+2, t=1, e_1=2n-1, v_1=e_i+1=2n$. So there are only one beautiful airline, and it forms a tree with $2n$ vertices. In this case, we can choose a beautiful airline edge, which satisfies the condition. Then $N<{{2n}\choose{2}}$, so there exists a pair $(P, Q)$ such that there are no $(P, Q)$-travel route with beautiful airline. There would be no beautiful airline if $P$ and $Q$ are in the same country, and otherwise there would be exactly one.

........

@above,Plz verify if I understand ur solution correctly. U basically consider $n$ monochromatic paths of length greater than one(one path for every pair $A_{i}$ and $B_{i}$).Also $m$ is the total number of colours these paths use.And for a colour $k$,$x_{k}$ denotes the number of such paths colored in $k$. But for a color $k$ ,with $x_{k}>1$,it may be that the starting edge of $C_{a}$ is the finishing edge of $C_{b}$,with both paths of colour $k$. Sorry ,if I made a mistake..

You are right. Starting and finishing edges can coincide, thanks.

genius09 wrote: Let $G_i=(V_i, E_i)$ be the graph of $i$th airline. If $G_i$ is disconnected, we can consider each components as different airlines. So I would change the statements that there are $m\geq n^2-2n+2$ airlines and each of them forms a connected graph. Denote the $i$th airline "good" if $|E_i|\geq2$. Let $t$ be the number of good airlines. Since each airline operates at least one flight, $1\leq t\leq n^2-m$. (The case $m=n^2$ is trivial, so assume $m<n^2$) Now we would count $N$, the number of airports pair $(P, Q)$ such that there exists a $(P, Q)$-travel route with a good airline. Without loss of generality, let good airlines be $1, 2, \cdots, t$. Since $G_i$ is connected, $v_i=|V_i|\leq |E_i|+1=e_i+1$. By double counting, $N\leq \sum_{i=1}^t{v_i \choose 2}\leq \sum_{i=1}^t {{e_i+1}\choose{2}}$. Also, $\sum_{i=1}^t e_i =n^2-m+t$, $e_i \geq 2$ for all $1\leq i\leq t$. Because of the concavity, $\sum_{i=1}^t {{e_i+1}\choose{2}}\leq (t-1){3\choose2}+{{n^2-m-t+3}\choose{2}}$. RHS is a quadratic function with axis $t=n^2-m-\frac{1}{2}$, so it is the maximum when $t=1$. Hence, $N\leq {{n^2-m+2}\choose{2}}\leq {{2n}\choose{2}}$. If the equality holds, $m=n^2-2n+2, t=1, e_1=2n-1, v_1=e_i+1=2n$. So there are only one beautiful airline, and it forms a tree with $2n$ vertices. In this case, we can choose a beautiful airline edge, which satisfies the condition. Then $N<{{2n}\choose{2}}$, so there exists a pair $(P, Q)$ such that there are no $(P, Q)$-travel route with beautiful airline. There would be no beautiful airline if $P$ and $Q$ are in the same country, and otherwise there would be exactly one.

genius09 wrote: Let $G_i=(V_i, E_i)$ be the graph of $i$th airline. If $G_i$ is disconnected, we can consider each components as different airlines. So I would change the statements that there are $m\geq n^2-2n+2$ airlines and each of them forms a connected graph. Denote the $i$th airline "good" if $|E_i|\geq2$. Let $t$ be the number of good airlines. Since each airline operates at least one flight, $1\leq t\leq n^2-m$. (The case $m=n^2$ is trivial, so assume $m<n^2$) Now we would count $N$, the number of airports pair $(P, Q)$ such that there exists a $(P, Q)$-travel route with a good airline. Without loss of generality, let good airlines be $1, 2, \cdots, t$. Since $G_i$ is connected, $v_i=|V_i|\leq |E_i|+1=e_i+1$. By double counting, $N\leq \sum_{i=1}^t{v_i \choose 2}\leq \sum_{i=1}^t {{e_i+1}\choose{2}}$. Also, $\sum_{i=1}^t e_i =n^2-m+t$, $e_i \geq 2$ for all $1\leq i\leq t$. Because of the concavity, $\sum_{i=1}^t {{e_i+1}\choose{2}}\leq (t-1){3\choose2}+{{n^2-m-t+3}\choose{2}}$. RHS is a quadratic function with axis $t=n^2-m-\frac{1}{2}$, so it is the maximum when $t=1$. Hence, $N\leq {{n^2-m+2}\choose{2}}\leq {{2n}\choose{2}}$. If the equality holds, $m=n^2-2n+2, t=1, e_1=2n-1, v_1=e_i+1=2n$. So there are only one beautiful airline, and it forms a tree with $2n$ vertices. In this case, we can choose a beautiful airline edge, which satisfies the condition. Then $N<{{2n}\choose{2}}$, so there exists a pair $(P, Q)$ such that there are no $(P, Q)$-travel route with beautiful airline. There would be no beautiful airline if $P$ and $Q$ are in the same country, and otherwise there would be exactly one. Since we want to count the number of good airlines,the inequality can be more specific: $N\leq \sum_{i=1}^t{v_i-1\choose 2}$ then we can be released from checking the conditions,which make the equality holds.