Let $n>1$ be an integer. A graph $G$ consists of $2n$ vertices and at least $n^2+1$ edges. Show that there exists at least $n$ triangles.
I already have a proof which is induction on $n$. But is there any direct method to do it?
UPDATE: Sketched inductive proof: Consider $n=k+1$ case. It can be shown there exists triangle $ABC$. Suppose in the rest of $2k-1$ points there are $P_A, P_B,P_C$ edges connecting to $A,B,C$ respectively.
- Case 1: $P_A+P_B+P_C \geq 3k-1$. It can be shown there are at least $k$ triangles taking one of $AB,BC,CA$ as edge, plus $ABC$, we get $k+1$ triangles.
- Case 2: $P_A+P_B+P_C \leq 3k-2$. Then one of $P_A+P_B, P_B+P_C,P_C+P_A$ must $\leq 2k-2$. Suppose $P_A+P_B \leq 2k-2$. One can show the other $2k-1$ points and C form a graph and have at least $(k+1)^2+1-(2k-2)-3=k^2+1$ edges ($3$ is from triangle $ABC$). By induction we have $k$ triangles, plus $ABC$, and we get $k+1$.