Prove that if there are $2n$ points and $n^2+1$ straight lines connecting them, then there are at least $n$ triangles in this shape.

127 Views Asked by At

Proof by induction.

For $n=2$, it says that if we have $2(2)=4$ points and $2^2+1=5$ lines connecting them to each other, then there are at least 2 triangles in this shape. Which is true (shown below) enter image description here

Let it be true for $n$ ($2n$ points and $n^2+1$ lines). Now here's the question, what about $n+1$? enter image description here