Proving the Existence of Triangle by Induction

Question

There is an exercise which is should be proven by induction:

$2n$ points are given in space. Altogether $n^2+1$ line segments are drawn between these points. Show that there is at least one set of three points which are joined pairwise by line segments.

I try to follow the induction steps.

For $n=2$(it's a minimal $n$ when we have three points), there are 4 points and 5 line segments. Maximum degree of the point is 3 (three line segments will connect this point to every other point) and one more segment will form a triangle between any two other points, therefore 4 segments is enough to form a triangle.

The assumption is correct for $n = k$.

$2k$ points, $k^2+1$ line segments.

Let's prove the assumption for the case when $n=k+1$ based on the fact that the assumption is true for $n=k$.

$n=k+1$,

$2n=2(k+1)=2k+2$ points, $2$ points more that for $n=k$.

$(k+1)^2+1=k^2+2k+2$ line segments, $2k+1$ line segments more than for $n=k$.

$2k+1$ line segments is enough to connect one of the addition 2 points to any other points (also to second additional point). However there are should be other line segments, and one of them will be enough for forming the triangle.

Is this proof correct and enough rigorous?

Answer 1

As you've set it up, there doesn't seem to be any geometric content. It's just asking you to prove Turan's Theorem. (There is a short, non-inductive proof of that.)

Anyway, as the comments mention, the last step as you have it is problematic. You want something like:

Suppose we have a set $P$ of $2n+2$ points and at least $(n+1)^2 + 1 = n^2 + 2n + 2$ segments. Let $ab$ be one of the segments given, and consider $P'=P\setminus \{a,b\}$. There are two cases: (a) $P'$ induces at least $n^2 + 1$ of the original segments; (b) it doesn't.

In case (a), we are done by the induction hypothesis right away.

In case (b), we see that at least $2n + 2$ of the original segments touch either $a$ or $b$. One of these is $ab$ itself, leaving at least $2n + 1$ segments running between $P'$ and $\{a,b\}$. Since $P'$ has only $2n$ points, there is some $c$ with a segment going to both $a$ and $b$. $abc$ makes the triangle we want.