Author |
Topic: Not just one triangle forced by many edges (Read 3517 times) |
|
ecoist
Senior Riddler
Gender: 
Posts: 405
|
 |
Not just one triangle forced by many edges
« on: Mar 9th, 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, K3, 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 10th, 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 (4E2/V - EV)/3 triangles. But this only gives 2/3 (n2+1)/n triangles in the V=2n case, and (n2+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 21st, 2007, 10:53am » |
Quote Modify
|
Interesting result. Seems hard to prove 
|
| « Last Edit: Mar 21st, 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 21st, 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 |n2/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 21st, 2007, 12:50pm » |
Quote Modify
|
on Mar 9th, 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 21st, 2007, 12:52pm » |
Quote Modify
|
For 2n vertices there are more than n2 edges, i.e atleast n2+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 21st, 2007, 1:57pm » |
Quote Modify
|
on Mar 21st, 2007, 12:52pm, Aryabhatta wrote:| For 2n vertices there are more than n2 edges, i.e atleast n2+1. |
|
Bleh, thats what i missed!
Thanks!
-- AI
|
| « Last Edit: Mar 21st, 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 22nd, 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 22nd, 2007, 9:05am » |
Quote Modify
|
on Mar 22nd, 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 22nd, 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
= 4E2/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 22nd, 2007, 4:47pm » |
Quote Modify
|
on Mar 22nd, 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 26th, 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) >= 4|E|^2/|V| - |E||V| = 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 non-empty 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 26th, 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 26th, 2007, 5:49pm » |
Quote Modify
|
Looks good!
We don't actually need "for sufficiently large n", since
|A|  3n,
|f(B)| E-|A| n2-n+2,
T = E/V (4E-V2) > (n+1)2/(2n+2)*4 = 2n+2,
so
f(A) T+|f(B)| n2+n+4 = (n-1)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 27th, 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 27th, 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 27th, 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 27th, 2007, 3:28pm » |
Quote Modify
|
Ok, here's hoping that this proof is error-free.
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)+1-k=k2+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 k2+1-d edges, which is greater than k2+1-k=(k-1)k+1. Hence G' has an extra edge to play with. By induction G' has k-1 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 k-1 triangles. These k-1 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 k2+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 k-1 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 k-1 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 27th, 2007, 4:09pm » |
Quote Modify
|
on Mar 27th, 2007, 3:28pm, ecoist wrote:Ok, here's hoping that this proof is error-free.
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)+1-k=k2+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 k2+1-d edges, which is greater than k2+1-k=(k-1)k+1. Hence G' has an extra edge to play with. By induction G' has k-1 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 k-1 triangles. These k-1 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 k2+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 k-1 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 k-1 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 27th, 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 27th, 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 1st, 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print