Prove that the number of pairs of edges that cross in a drawing of $K_n$ is at least $\frac{1}{5}\binom{n}{4}$ (for $n\geq 5$) Here, $K_n$ is the complete graph on $n$ vertices.
The only thing I can think of is induction on the number of vertices. The claim holds for $n=5$; this is easy to check. I was thinking of assuming that it holds for $n-1$ and then consider a drawing of $K_{n-1}$ with a minimal number of crossings. Then add a vertex at each crossing to form a planar graph $L$, and then somehow get a lower bound $k$ on the size of a face $L$. Then when you add a vertex to $K_{n-1}$ to form $K_n$ it is in one of the faces of $L$, and it adds at least $n-1-k$ crossings.
But I can't get this to work out at all and I suspect it's a completely dead end.
 A: Pick any five vertices. Then, as $K_5$ is not planar, there is a pair of edges in the graph generated by these 5 vertices which cross. 
Thus, we get at least one crossing for every combination of $5$ vertices. In total, our count is at least $\binom{n}{5}$.
But, we might had counted the same crossing multiple times. Look at a crossing: lets say $v_iv_j$ and $v_kv_l$.We counted this crossing at most $n-4$ times: we might have counted it in the quintle $v_i v_j v_k v_l v_s$ where $1 \leq s \leq n$ and $s \neq i, s \neq j , s\neq l s\neq m$. 
If $k$ is the number of crossings, and we counted each crossing at most $n-4$ times, our count is at most $k(n-4)$. Thus
$$k(n-4) \geq \binom{n}{5}\,.$$
Thus the number of crossings is at least 
$$\frac{\binom{n}{5}}{n-4}=\frac{1}{5}\binom{n}{4}$$
A: A crossing in a drawing of $K_n$ is an unordered pair $\{e,f\}$ of edges which cross each other but have no endpoint in common, i.e., they have $4$ distinct endpoints between them. If $x=\{e,f\}$ is a crossing, let $V(X)$ be the set consisting of the $4$ endpoints of $e$ and $f$.
Let $f(n)$ be the crossing number of $K_n$, i.e., the minimum possible number of crossings in a drawing of $K_n$ in the plane. We know that$f(5)=\frac15\binom54$. In order to prove that $f(n)\ge\frac15\binom n4$ for all $n\ge5$, it will suffice to show that $f(n)/\binom n4$ is a nondecreasing function of $n$.
Consider any $n\ge5$. I want to show that $f(n)/\binom n4\ge f(n-1)/\binom{n-1}4$, i.e., that $(n-4)f(n)\ge nf(n-1)$.
Consider a drawing of $K_n$ with exactly $f(n)$ crossings. Let $S$ be the set of all pairs $(X,v)$ such that $X$ is a crossing in $K_n$ and $v$ is a vertex in $V(K_n)\setminus V(X)$. Choosing $X$ first, we see that $|S|=(n-4)f(n)$. Choosing $v$ first, we see that $|S|\ge nf(n-1)$. Thus $(n-4)f(n)\ge nf(n-1)$, Q.E.D.
Since $f(5)=1$, it follows that $f(n)\ge\frac15\binom n4$ for all $n\ge5$. Likewise, if we know (e.g. from OEIS or Wikipedia) that $f(7)=9$, it follows that $f(n)\ge\frac9{35}\binom n4$ for all $n\ge7$. Moreover, it is easy to see that there is a constant $c\gt0$ such that $f(n)\sim c\binom n4\sim\frac n{24}n^4$ as $n\to\infty$. The same arguments apply, e.g., to the rectilinear crossing number of $K_n$, i.e., the minimum number of crossings in a drawing of $K_n$ in which edges are drawn as straight line segments.
