Triangle in a 2n-Graph

For discussing Olympiad Level Combinatorics problems
User avatar
sowmitra
Posts:155
Joined:Tue Mar 20, 2012 12:55 am
Location:Mirpur, Dhaka, Bangladesh
Triangle in a 2n-Graph

Unread post by sowmitra » Mon Feb 16, 2015 6:46 pm

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.
"Rhythm is mathematics of the sub-conscious."
Some-Angle Related Problems;

User avatar
nayel
Posts:268
Joined:Tue Dec 07, 2010 7:38 pm
Location:Dhaka, Bangladesh or Cambridge, UK

Re: Triangle in a 2n-Graph

Unread post by nayel » Tue Feb 17, 2015 12:12 pm

This is Mantel's theorem, a special case of a more general theorem of Turan. Let us prove the following version.
We prove by induction on $n$ that any graph $G$ with $n$ vertices and $>n^2/4$ edges contains a triangle. If every vertex has degree $\ge (n-1)/2$ then any two vertices must have a common neighbour, yielding a triangle. So assume that there is a vertex $v$ of degree $<(n-1)/2$. If $G'$ is the graph obtained by deleting $v$ from $G$, then the number of edges in $G'$ is $>n^2/4-(n-1)/2>(n-1)^2/4$. Hence by the induction hypothesis $G'$ contains a triangle, and so $G$ does too. I leave the base case to be checked.

The bound is in fact the best possible. To see this consider the complete bipartite graph $K_{\lceil n/2\rceil,\lfloor n/2\rfloor}$.
"Everything should be made as simple as possible, but not simpler." - Albert Einstein

Tahmid
Posts:110
Joined:Wed Mar 20, 2013 10:50 pm

Re: Triangle in a 2n-Graph

Unread post by Tahmid » Thu Feb 19, 2015 12:22 am

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 :? :?:

Post Reply