Prove that a simple graph with $2n$ vertices without triangles has at most $n^2$ lines. Prove that a simple graph with $2n$ vertices without triangles has at most $n^2$ lines.
I've been struggling with this exercise for some time, but I can't come up with a decent proof. 
 A: Hint: Show if two nodes have an edge between them, then the degrees of those two nodes must add up to at most $2n$.
If you remove those two nodes from the graph, you have a graph with $2(n-1)$ nodes and no triangles. From the first line, how many edges do you remove, at most? Proceed by induction.
A: I answered the other question, but here is a totally different kind of argument.
Fact: If $G$ has $n$ vertices and $m$ edges, then it has an independent set of size at least $n/(D+1)$, where $D=2m/n$ is the average degree.
To see how this implies your statement, consider switching the edges and non-edges of $G$ to get the graph complement.  If this has an independent set of size $3$, $G$ had a triangle.  On the other hand, if $G$ has at least $n^2 + 1$ edges, then, for the complement, $D < n - 1$, so $2n/(D + 1) > 2$.
A slick proof (I've heard it attributed to Ravi Boppana) of the fact is: uniformly shuffle the vertices of $G$ and then select each vertex that appears before all of its neighbors to get a subset $I$.  This $I$ is an independent set and, since each vertex $v$ is first among its $d_v$ neighbors with probability $(d_v + 1)^{-1}$, the expected size of $I$ is 
$$
\sum_{i\in V(G)} \frac{1}{d_i + 1} \ge \frac{n}{D+1}
$$
with the inequality coming from symmetry and convexity.
