Between $n$ cities there are $\frac{1}{2}n^2-\frac{3}{2}n+2$ direct flight connections which can be used in both directs (From city A to city B and vice versa). There can't be two connections from one city to another (no multiple edges).
Prove that you can fly from any city to any other without changing planes more than once.
Attempt
This seems like a graph theory exercise. I added the interpretation in the brackets, we have a simple graph with $n$ knots and $\frac{1}{2}n^2-\frac{3}{2}n+2$ edges. But what's the graph theory equivalent of saying "without changing planes more than once". Does it mean you can reach every vertex by a path with maximum length of $2$?
Best Answer
Complete graph of $n$ vertices has $\frac{1}{2}n^2-\frac{1}{2}n$ edges.
Suppose that there are two cities $A_1$ and $A_2$ that cannot be reached one from other with path of length 1 or 2. Then there is no edge between cities $A_1$ and $A_2$. For each of other $n-2$ cities $A_3,A_4,...,A_n$ there is at most one edge connecting this city $A_i$ with $A_1$ or $A_2$ otherwise there is path $A_1A_iA_2$ of length 2, connecting $A_1$ and $A_2$. Then total number of pairs $A_kA_n$ which are not connected by direct flight is at least $1+(n-2)=n-1$. Then number of direct flight connections is at most $\frac{1}{2}n^2-\frac{1}{2}n-(n-1)=\frac{1}{2}n^2-\frac{3}{2}n+1$. This fact contradicts condition that's why suppose is wrong.