- #1
- 4,699
- 369
I am given a graph G with 1000 vertices and 250,001 edges and I need to show there are two triangles in it with common edge.
Now if I write the graph of 'two triangles with a common edge' as H then I need to show that:
[tex]ex(1000,H) \le ex(1000, K_3) = 250,000[/tex]
So basically I need to show that the set
[tex] F_1=\{ |E(G)| : |V(G)|=1000, H\not\subset G\}[/tex]
is a subset of [tex] F_2=\{|E(G)| : |V(G)|=1000, K_3 \not\subset G\}[/tex]
Now, I am not sure if my reasoning is correct, but I think that if K_3 isn't a subgraph of G then obviously H isn't as well (cause G doesn't contain triangles), so it seems to me that F_2 is a subset of F_1 and not the other way around?
Have I got it all wrong here?
Now if I write the graph of 'two triangles with a common edge' as H then I need to show that:
[tex]ex(1000,H) \le ex(1000, K_3) = 250,000[/tex]
So basically I need to show that the set
[tex] F_1=\{ |E(G)| : |V(G)|=1000, H\not\subset G\}[/tex]
is a subset of [tex] F_2=\{|E(G)| : |V(G)|=1000, K_3 \not\subset G\}[/tex]
Now, I am not sure if my reasoning is correct, but I think that if K_3 isn't a subgraph of G then obviously H isn't as well (cause G doesn't contain triangles), so it seems to me that F_2 is a subset of F_1 and not the other way around?
Have I got it all wrong here?
Last edited: