# Proving the Existence of Triangle by Induction

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?

-
Maybe somewhere it should be explicitly stated that the points cannot all lie on a line? If all of these points are on the $x$-axis, say, then there won't be a triangle. – anon271828 Feb 19 '13 at 14:35
@anon271828 from the phrasing of the question, degenerate triangles count as triangles. – Willie Wong Feb 19 '13 at 14:53
The final step is not correct. You are trying to construct a way to place the edges so that a triangle is formed. But the question is to show that any placement of $(k+1)^2+1$ lines among $2k+2$ points forms a triangle. Start with $2k+2$ points and $(k+1)^2+1$ lines. Remove any two points connected by a line. Now show that either the remaining $2k$ points have a triangle, or there are enough lines touching these two points such that any way they are placed, they will form a triangle. – polkjh Feb 19 '13 at 15:07
Actually, your idea to start with $n=2$ is not ok. The problem statement does not exclude the case $n=1$ (or the case $n=0$). Can you see why the claim is still true for these values of $n$ even though we cannot possibly have a triangle? – Hagen von Eitzen Feb 19 '13 at 17:17

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.

-
Thank you very much for the answer, but why actually "at least $2n+2$ of the original segments touch either a or b"? – fog Feb 22 '13 at 5:23
There are at least $n^2+2n+2$ in total, and we are assuming that at most $n^2$ of them are entirely in $P'$ (otherwise we'd have been in case (a)). – Louis Feb 22 '13 at 14:54