Author 
Topic: Not just one triangle forced by many edges (Read 3511 times) 

ecoist
Senior Riddler
Gender:
Posts: 405


Not just one triangle forced by many edges
« on: Mar 9^{th}, 2007, 11:58pm » 
Quote Modify

Slight generalization of a known result: Let G be an undirected graph with 2n+e vertices, e equal 0 or 1, and with no loops or multiple edges. Show that, if G contains more than n(n+e) edges, then G contains at least n triangles. (A triangle is three vertices, every two of which are joined by an edge; that is, the complete graph, K_{3}, on three vertices)


IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Not just one triangle forced by many edges
« Reply #1 on: Mar 10^{th}, 2007, 6:27pm » 
Quote Modify

There is a pretty simple argument that in a graph with V vertices and E edges, there must be at least (4E^{2}/V  EV)/3 triangles. But this only gives 2/3 (n^{2}+1)/n triangles in the V=2n case, and (n^{2}+n+1)/(2n+1) in the V=2n+1 case.


IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Not just one triangle forced by many edges
« Reply #2 on: Mar 21^{st}, 2007, 10:53am » 
Quote Modify

Interesting result. Seems hard to prove

« Last Edit: Mar 21^{st}, 2007, 10:53am by Aryabhatta » 
IP Logged 



ecoist
Senior Riddler
Gender:
Posts: 405


Re: Not just one triangle forced by many edges
« Reply #3 on: Mar 21^{st}, 2007, 12:20pm » 
Quote Modify

I first encountered this problem when a Georgia Tech student gave me his homework exercise to prove: Given a graph G with 10 vertices and 26 edges, show that G contains a triangle. I fooled around and found that G contains at least 5 triangles, and discovered that it was easier to solve the posted problem than just this special case. Turan's Theorem implies that, if a graph G with n vertices contains more than n^{2}/4 edges, then G contains a triangle (Mantel's Theorem).


IP Logged 



TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001


Re: Not just one triangle forced by many edges
« Reply #4 on: Mar 21^{st}, 2007, 12:50pm » 
Quote Modify

on Mar 9^{th}, 2007, 11:58pm, ecoist wrote:Let G be an undirected graph with 2n+e vertices, e equal 0 or 1, and with no loops or multiple edges. Show that, if G contains more than n(n+e) edges, then G contains at least n triangles. 
 I didnt ask this earlier because it sounds too stupid, but since its not solved yet, let me ask it anyway. How does the above work for n=2 and e=0? I mean for 4 vertices and 4 edges, one can arrange them in a square? Similarly, for e=1, if i arrange the 5 vertices and 5/6 edges as a pentagon and then connect any two for the 6th edge, then it gives me atmost one triangle? I must be doing something really stupid here, please clarify the question for me.  AI


IP Logged 
Self discovery comes when a man measures himself against an obstacle  Antoine de Saint Exupery



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Not just one triangle forced by many edges
« Reply #5 on: Mar 21^{st}, 2007, 12:52pm » 
Quote Modify

For 2n vertices there are more than n^{2} edges, i.e atleast n^{2}+1. In case of 4 vertices, there must be 5 edges.


IP Logged 



TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001


Re: Not just one triangle forced by many edges
« Reply #6 on: Mar 21^{st}, 2007, 1:57pm » 
Quote Modify

on Mar 21^{st}, 2007, 12:52pm, Aryabhatta wrote:For 2n vertices there are more than n^{2} edges, i.e atleast n^{2}+1. 
 Bleh, thats what i missed! Thanks!  AI

« Last Edit: Mar 21^{st}, 2007, 1:57pm by TenaliRaman » 
IP Logged 
Self discovery comes when a man measures himself against an obstacle  Antoine de Saint Exupery



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Not just one triangle forced by many edges
« Reply #7 on: Mar 22^{nd}, 2007, 1:33am » 
Quote Modify

Ok. Here is an attempt to prove the 2n part. It is very late here, so please pardon any goofs. We try to prove by induction on n. Suppose we are given a graph of 2n+2 vertices with at least (n+1)^2 + 1 edges. There is at least one triangle in this graph. We can show that there is some edge e = {u,v} of this graph such that e is the edge of exactly one triangle. Suppose there are k triangles, this implies that there are at least 2k+1 edges which form an edge of the triangle. If each edge is an edge of at least 2 triangles, then there are atleast 2(2k+1)/3 triangles. We can also show that d(u)1 + d(v)1 <= 2n+1 (if it were at least 2n+2, then {u,v} would form at least 2 triangles) Thus if we remove vertices u and v (and the edges bordering u and v), we are left with a graph of 2n vertices and at least n^2+1 edges. By induction assumption this has at least n triangles. Thus if we also count the triangle of which {u,v} is a part, there are at least n+1 triangles.


IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Not just one triangle forced by many edges
« Reply #8 on: Mar 22^{nd}, 2007, 9:05am » 
Quote Modify

on Mar 22^{nd}, 2007, 1:33am, Aryabhatta wrote: We can also show that d(u)1 + d(v)1 <= 2n+1 (if it were at least 2n+2, then {u,v} would form at least 2 triangles) Thus if we remove vertices u and v (and the edges bordering u and v), we are left with a graph of 2n vertices and at least n^2+1 edges. 
 Ack! This part looks wrong. Back to the board.


IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Not just one triangle forced by many edges
« Reply #9 on: Mar 22^{nd}, 2007, 12:08pm » 
Quote Modify

The result I mentioned earlier can be shown as follows: By pigeonholing, the number of triangles containing a given edge (x,y) is at least d(x) + d(y)  V. Summing this over all edges, we have 3T _{(x,y)} (d(x) + d(y)  V) = d(x)^{2}  EV (d(x))^{2} / V  EV = 4E^{2}/V  EV. This result isn't strong enough though. To try to strengthen it, one might consider where equality could possibly hold in the two inequalities above. The first inequality is strict unless every vertex is connected to at least one of x and y, for every edge (x,y). The second is strict unless every vertex has the same degree.


IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Not just one triangle forced by many edges
« Reply #10 on: Mar 22^{nd}, 2007, 4:47pm » 
Quote Modify

on Mar 22^{nd}, 2007, 1:33am, Aryabhatta wrote:Suppose there are k triangles, this implies that there are at least 2k+1 edges which form an edge of the triangle. 
 This seems wrong too!


IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Not just one triangle forced by many edges
« Reply #11 on: Mar 26^{th}, 2007, 12:46pm » 
Quote Modify

I hope this is right... (Can someone please verify it?) Let us try to prove the 2n case by induction on n. Assume true for any graph with 2n vertices and at least n^2 +1 edges. Assume we are given a graph G(V,E) with 2n+2 vertices and at least (n+1)^2 + 1 edges. Suppose there is some edge {u,v} which is an edge of a triangle (there exists one, Mantel's theorem) such that d(u) + d(v) <= 2n+2 (d(w) is degree of vertex w) Then, by deleting vertices u and v, we obtain a graph G' with 2n vertices and at least n^2 + 1 edges. Thus G' has at least n triangles, and hence G must have at least n+1 triangles. Now suppose that for every edge {u,v} which is part of a triangle, d(u) + d(v) > 2n+2  (1) for edge e = {x,y} define f(e) = d(x) + d(y)  (2n+2) For any edge set E' subset of E define f(E') = Sum_{e in E'} f(e) Let A = {e  f(e) > 0} B = { e  f(e) < 0} C = {e  f(e) = 0} By (1), Any edge e, which is some edge of a triangle is in A. if t is the number of triangles in G, then we have that 3t >= f(A) Thus is A >= 3n we are done. So assume A < 3n Now if C = 0 (i.e C is empty) the f(B) > n^2  2n (as A < 3n) Eigenray's post shows that f(A) + f(B) >= 4E^2/V  EV = T say (which is at least 2n) i.e if C = 0 then f(A) >= T + f(B) > 3n for sufficiently large n. (as T >= 2n and f(B) > n^2  2n) Thus, if t < n, then C must be nonempty i.e there must be at least one edge e in E such that f(e) = 0, say f ({s,t}) = 0 Thus we have that d(s) + d(t) = 2n+2 Let N(u) = neighbours of vertex u. Now N(s)  {t} Union N(t)  {s} is exactly the remaining 2n vertices. We can show that either s or t must be the vertex of some triangle. (if not, then the graph is "bipartite" on the remaining 2n vertices + extra 2 vertices (and 2n+1 edges), which gives number of edges <= (n+1)^2) (any bipartite graph on 2n vertices cannot have more than n^2 edges) Thus is we now delete the vertices s,t (and corresponding edges) we get a Graph G' which has at least n triangles. Since deleting s and t deletes somes triangle of G, we are done. The odd case can be derived from this i guess. (haven't thought about it).

« Last Edit: Mar 26^{th}, 2007, 4:22pm by Aryabhatta » 
IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Not just one triangle forced by many edges
« Reply #12 on: Mar 26^{th}, 2007, 5:49pm » 
Quote Modify

Looks good! We don't actually need "for sufficiently large n", since A 3n, f(B) EA n^{2}n+2, T = E/V (4EV^{2}) > (n+1)^{2}/(2n+2)*4 = 2n+2, so f(A) T+f(B) n^{2}+n+4 = (n1)^{2} + 3n+3 3(n+1).


IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Not just one triangle forced by many edges
« Reply #13 on: Mar 27^{th}, 2007, 10:38am » 
Quote Modify

Thanks Eigenray for verifying the proof. ecoist, can you please provide us with the proof you have? The above proof is not very appealing...

« Last Edit: Mar 27^{th}, 2007, 10:47am by Aryabhatta » 
IP Logged 



ecoist
Senior Riddler
Gender:
Posts: 405


Re: Not just one triangle forced by many edges
« Reply #14 on: Mar 27^{th}, 2007, 11:54am » 
Quote Modify

Perhaps this evening. Have to come down from arguing with someone online about the war. Also need to double check my solution. Discovered last night that my solution contained an error, which I corrected this morning (couldn't find my original solution developed years ago).


IP Logged 



ecoist
Senior Riddler
Gender:
Posts: 405


Re: Not just one triangle forced by many edges
« Reply #15 on: Mar 27^{th}, 2007, 3:28pm » 
Quote Modify

Ok, here's hoping that this proof is errorfree. Induction on k. The result is true for k<2. Assume that k>2 and that, for all t<k, if a graph has 2t+e vertices and more than t(t+e) edges, then it has at leat t triangles. Let G be a graph with 2k+e vertices and more than k(k+e) edges. Without loss we may assume G has exactly k(k+e)+1 edges. Since the sum of the degrees of the vertices of G equals twice the number of its edges, it follows that the average degree of a vertex of G is (*) 2(k(k+e)+1)/(2k+e)=k+(ek+2)/(2k+e)<k+1. because K>2) Hence G has a vertex v of degree less or equal k. Suppose first that e=1. Let G' be the subgraph of G omitting vertex v and the edges containing v. Then G' has 2k vertices and at least k(k+1)+1k=k^{2}+1 edges. Hence, by induction, G' has k triangles; whence so does G. Now suppose e=0. If there is a vertex w in G of degree d less than k, then the subgraph G' omitting w and the edges containing w has k^{2}+1d edges, which is greater than k^{2}+1k=(k1)k+1. Hence G' has an extra edge to play with. By induction G' has k1 triangles. Let {x,y,z} be one of those triangles. If we remove the edge {x,y} from G' to obtain the subgraph G'', then G'' still has enough edges to guarantee k1 triangles. These k1 triangles together with the triangle {x,y,z} are k triangles in G. If there is no vertex in G of degree less than k, then, since there are only k^{2}+1 edges, there are at most two vertices of degree greater than k (see (*)). Let v be a vertex in G of degree k. Then, by induction, the subgraph G' of G omitting v has k1 triangles. Let {x,y,z} be one of these triangles. Then, one of these vertices, say x, has degree k. Hence, by induction, the subgraph G* of G omitting x has k1 triangles. These triangles together with the triangle {x,y,z} insures that G contains k triangles. The induction is complete.


IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Not just one triangle forced by many edges
« Reply #16 on: Mar 27^{th}, 2007, 4:09pm » 
Quote Modify

on Mar 27^{th}, 2007, 3:28pm, ecoist wrote:Ok, here's hoping that this proof is errorfree. Induction on k. The result is true for k<2. Assume that k>2 and that, for all t<k, if a graph has 2t+e vertices and more than t(t+e) edges, then it has at leat t triangles. (*) 2(k(k+e)+1)/(2k+e)=k+(ek+2)/(2k+e)<k+1. because K>2) 
 OK. Quote: Hence G has a vertex v of degree less or equal k. Suppose first that e=1. Let G' be the subgraph of G omitting vertex v and the edges containing v. Then G' has 2k vertices and at least k(k+1)+1k=k^{2}+1 edges. Hence, by induction, G' has k triangles; whence so does G. 
 At first I was confused (because you need to show that 2k vertex graph has k triangles), but, this follows because of the proof for e=0. Considering e=0 before e=1 might make it less confusing. Quote: Now suppose e=0. If there is a vertex w in G of degree d less than k, then the subgraph G' omitting w and the edges containing w has k^{2}+1d edges, which is greater than k^{2}+1k=(k1)k+1. Hence G' has an extra edge to play with. By induction G' has k1 triangles. Let {x,y,z} be one of those triangles. If we remove the edge {x,y} from G' to obtain the subgraph G'', then G'' still has enough edges to guarantee k1 triangles. These k1 triangles together with the triangle {x,y,z} are k triangles in G. 
 Looks fine. Quote: If there is no vertex in G of degree less than k, then, since there are only k^{2}+1 edges, there are at most two vertices of degree greater than k (see (*)). Let v be a vertex in G of degree k. Then, by induction, the subgraph G' of G omitting v has k1 triangles. Let {x,y,z} be one of these triangles. Then, one of these vertices, say x, has degree k. Hence, by induction, the subgraph G* of G omitting x has k1 triangles. These triangles together with the triangle {x,y,z} insures that G contains k triangles. The induction is complete. 
 Or simply just consider a triangle {x,y,z} in G. Since at most 2 have degree > k, at least one has degree k, say x. Deleting x, the result follows by induction. There is no need to consider v etc. Overall, it looks good to me. Very nice proof!

« Last Edit: Mar 27^{th}, 2007, 4:15pm by Aryabhatta » 
IP Logged 



ecoist
Senior Riddler
Gender:
Posts: 405


Re: Not just one triangle forced by many edges
« Reply #17 on: Mar 27^{th}, 2007, 5:41pm » 
Quote Modify

Thanks, Aryabhatta! Quote:At first I was confused (because you need to show that 2k vertex graph has k triangles), but, this follows because of the proof for e=0. Considering e=0 before e=1 might make it less confusing. 
 Sorry. the induction is on k, not the number of vertices in G. I chose to do e=1 first only because it is the easiest case. Quote: Or simply just consider a triangle {x,y,z} in G. Since at most 2 have degree > k, at least one has degree k, say x. Deleting x, the result follows by induction. There is no need to consider v etc. 
 If there are vertices of degree less than k, then there could be more than 2 vertices of degree greater than k.


IP Logged 



ecoist
Senior Riddler
Gender:
Posts: 405


Re: Not just one triangle forced by many edges
« Reply #18 on: Apr 1^{st}, 2007, 3:23pm » 
Quote Modify

On second thought, you are right, Aryabhatta, for being concerned that I looked at the case e=1 first! If, as I said, the induction is on k, then the induction step does not apply when e=1, because k retains its value when a vertex is removed. I should have done the case e=0 first.


IP Logged 



