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$.
$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?