Prove that there is at least one triangle. Suppose that $2n$ points are given in space where $n\geq 2$. And $n^2+1$ line segments are drawn between these points. Prove that there is at least one triangle.(a set of three points which are joined pairwise by line segments)
Let $d(p)$ be the number of other points that $p$ is connected to by line segments. If $p$ and $q$ are connected by a line segment, and $d(p) + d(q) > 2n-2$, then pigeonhole principle implies there's some third point $r$ such that $p,q,r$ form a triangle. 
Would this be a fair approach my hint was to try induction but i'm unsure how to proceed that way. 
 A: The inductive approach uses the fact that you've observed.  Let's see a sketch:
Base Case:

 When $n=2$, there are $4$ points and $5$ edges.  Since there are $\binom{4}{2}=6$ possible edges, all but one edge appears.  Let the four points be $\{p,q,r,s\}$ and $pq$ the edge that doesn't appear.  Then, $\{p,r,s\}$ forms a triangle.

Inductive Case:

 Assume the claim is true when $n=k$ and consider the case where $n=k+1$.  Observe that $(k+1)^2+1=k^2+2k+2$ has $2k+1$ more edges than the $n=k$ case.  Let $p$ and $q$ be two points that are connected by an edge.  Let $d(p)$ be the number of edges incident to $p$ and $d(q)$ be the number of edges incident to $q$.

When there are a large number of edges:  

 If $d(p)+d(q)>2k+2$, then $p$ and $q$ make a triangle with some third point by the pigeonhole principle. ($d(p)-1$ is the number of edges leaving $p$ and not going to $q$, $d(q)-1$ is the number of edges leaving $q$ and not going to $p$, and there are $2k$ other vertices).

When there are a small number of edges:

 If $d(p)+d(q)\leq 2k+2$, then between the $2k$ points other than $p$ and $q$, there are $k^2+1$ edges (remember that $d(p)+d(q)$ double counts the edge between them).  Then, you can use the inductive hypothesis.  

