Lets take two maximum paths $l_1,l_2$ If two don't share a vertex, lets take the shortest path connecting some two vertices in $l_1,l_2$ and call it $l_3$ $l_3$ connects $A_i,B_j$ $WLOG$ $i,j \ge \frac{M}{2}$ Think about $A_M ,...,A_i (l_3) B_j,...,B_M$ contradiction If two share only one vertex, it is $ A_{\frac{M}{2}}=B_{\frac{M}{2}}=C$ think about paths connecting any two of $A_i(i\ge\frac{M}{2})$, $A_i(i\leq\frac{M}{2})$, $B_i(i\ge\frac{M}{2})$, $B_i(i\leq\frac{M}{2})$ Using a similar way, there leads a contradiction

chrono223 wrote: $ $ $ $ $ $ $ $There is a group of more than three airports. For any two airports $A, B$ belonging to this group, if there is an aircraft from $A$ to $ $ $B$, there is an aircraft from $B$ to $ $ $A$. For a list of different airports $A_0,A_1,...A_n$, define this list as a 'route' if there is an aircraft from $A_i$ to $A_{i+1}$ for each $i=0,1,...,n-1$. Also, define the beginning of this route as $A_0$, the end as $A_n$, and the length as $n$. ($n\in \mathbb N$) $ $ $ $ $ $ $ $Now, let's say that for any three different pairs of airports $(A,B,C)$, there is always a route $P$ that satisfies the following condition. $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ Condition: $P$ begins with $A$ and ends with $B$, and does not include $C$. $ $ $ $ $ $When the length of the longest of the existing routes is $M$ ($\ge 2$), prove that any two routes of length $M$ contain at least two different airports simultaneously. We give this problem a graph theoretical representation, the airports being the vertices and the edges denote the aeroplane service between two airports, so if vertices $u$ and $v$ have a common edge incident to both the vertices then the airports represented by vertices $u$ and $v$ have aeroplane service available directly from one airport to other and vice versa. We call a route as 'cycl; for our convenience. Consider two maximal cycls $C_1$ and $C_2$. We see that if $V(C_1) \cap V(C_2) = \varnothing$ then consider the smallest path (cycl) that connects two vertices $u$ and $v$ (exists according to the conditions of the problem) +where $u \in C_1$ and $v \in C_2$ and observe that we can form a huger cycle out of $C_1$, $C_2$ and the path from $u$ and $v$ which contradicts the maximality of $C_1$ and $C_2$. Therefore, $V(C_1) \cap V(C_2) \geq 1$. For the sake of contradiction let us say that $V(C_1) \cap V(C_2) = 1$ for all such selections of $C_1$ and $C_2$. Observe that $2 \lvert M + 1= \lvert V(C_1) \rvert + 1$ and given a maximal cycl, we observe that every maximal cycl must contain a common vertex, and if we number the vertices of a maximal cycl as $v_1, v_2, v_3 \dots v_M$, then the vertex $v_{\frac{M+1}{2}}$ is common to every other cycl or similarly like the previous case we can finish easily. However, there must be a cycl (path) from $v_1$ to $v_M$ not including $v_{\frac{M+1}{2}}$ and therefore there should exist a cycl with larger number of vertices than $C_1$ or $C_2$ which contradicts the maximality of $M = \lvert v(C_1) \rvert$ and hence we are done.