Triangle in a 2n-Graph
There are $2n$ points in space such that no $3$ points are co-linear. Suppose, they are joined by at least $n^2+1$ edges. Show that, at least $1$ triangle is formed.
Re: Triangle in a 2n-Graph
This is Mantel's theorem, a special case of a more general theorem of Turan. Let us prove the following version.
"Everything should be made as simple as possible, but not simpler." - Albert Einstein
Re: Triangle in a 2n-Graph
it is easy to check that it works for $n=2$
let it is true for $n=m$ ......
now for $n=m+1$
we have $2(m+1)=2m+2$ points and we need to connect $m^{2}+2m+2$ edges
let there are $2m+2$ points in a plane such that no three are collinear ....
now draw an area S such that $2m$ points are inside S.
other 2 are outside of S . [let they are A and B ] .
we can draw $m^{2}$ edges among 2m points in S sush that no triangle creates ....
now come to A and B .....we can join A with $m$ points among $2m$ points in S ..... and can join B with the rest .... and can join A with B ....
here we have $2m+1$ edges .....
we need one more edge .....
case 1 : it is created by joining two points in S [then S have $m^{2}+1$ edges ..... so a triangle will be formed ]
case 2 : it is created by joining two points, one in S (let it is P) and one is A or B .... [notice that first we joined A (or B) with P .... here we joined B (or A) with P . so P have edges with A and B both . so a triangle PAB will form ]
so , we proved the property for $n=m+1$
by induction ....done!!! .....
is my solution right? ...pls anyone check
let it is true for $n=m$ ......
now for $n=m+1$
we have $2(m+1)=2m+2$ points and we need to connect $m^{2}+2m+2$ edges
let there are $2m+2$ points in a plane such that no three are collinear ....
now draw an area S such that $2m$ points are inside S.
other 2 are outside of S . [let they are A and B ] .
we can draw $m^{2}$ edges among 2m points in S sush that no triangle creates ....
now come to A and B .....we can join A with $m$ points among $2m$ points in S ..... and can join B with the rest .... and can join A with B ....
here we have $2m+1$ edges .....
we need one more edge .....
case 1 : it is created by joining two points in S [then S have $m^{2}+1$ edges ..... so a triangle will be formed ]
case 2 : it is created by joining two points, one in S (let it is P) and one is A or B .... [notice that first we joined A (or B) with P .... here we joined B (or A) with P . so P have edges with A and B both . so a triangle PAB will form ]
so , we proved the property for $n=m+1$
by induction ....done!!! .....
is my solution right? ...pls anyone check