Prove that a simple graph with $2$ vertices without triangles inside has at most $n^2$ lines.

Question

A triangle in a graph is a subset of the node set $\{a, b, c\} \subseteq V (G)$ such that $\{a, b\}, \{a, c\}, \{b, c\} \in E (G).$ Prove with induction for all $n \in \mathbb{N}$ that a graph without a triangle with $2n$ nodes has at most $n^2$ edges.

Answer 1

The crucial part of the proof is to choose two vertices $u,v$ say, which are connected. Then there are at most $2n-2$ edges from these points to other points (they cannot both be joined to the same point).

Then by induction the number of edges is at most $1+(2n-2)+(n-1)^2=n^2$.