Proving the Existence of Two Triangles with Common Edge in a 1000-Vertex Graph

  • Context: Graduate 
  • Thread starter Thread starter MathematicalPhysicist
  • Start date Start date
  • Tags Tags
    Graph
Click For Summary
SUMMARY

This discussion centers on proving the existence of two triangles with a common edge in a graph G containing 1000 vertices and 250,001 edges. The user aims to demonstrate that the edge count of G, denoted as ex(1000,H), is less than or equal to ex(1000,K_3), which equals 250,000. The user proposes that if K_3 is not a subgraph of G, then H cannot be a subgraph either, suggesting a misunderstanding of the relationships between the sets F_1 and F_2. Clarification is sought regarding the reasoning process and the implications of subgraph inclusion.

PREREQUISITES
  • Understanding of graph theory concepts, particularly subgraphs and edge counts.
  • Familiarity with the Erdős–Szekeres theorem and extremal graph theory.
  • Knowledge of the notation ex(n, H) for extremal graph problems.
  • Basic skills in logical reasoning and proof techniques in mathematics.
NEXT STEPS
  • Study the Erdős–Szekeres theorem to understand extremal graph theory better.
  • Research the properties of K_3 and its implications in graph structures.
  • Explore the concept of subgraph inclusion and its significance in graph theory.
  • Learn about the techniques for proving the existence of specific subgraphs in large graphs.
USEFUL FOR

Mathematicians, computer scientists, and students studying graph theory, particularly those interested in extremal graph problems and subgraph properties.

MathematicalPhysicist
Science Advisor
Gold Member
Messages
4,662
Reaction score
372
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:
ex(1000,H) \le ex(1000, K_3) = 250,000

So basically I need to show that the set
F_1=\{ |E(G)| : |V(G)|=1000, H\not\subset G\}
is a subset of F_2=\{|E(G)| : |V(G)|=1000, K_3 \not\subset G\}

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:
Physics news on Phys.org
Anyone?
Where have I gone wrong here?

Cheers!
 

Similar threads

Replies
1
Views
2K
  • · Replies 3 ·
Replies
3
Views
1K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 6 ·
Replies
6
Views
2K
  • · Replies 6 ·
Replies
6
Views
2K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 1 ·
Replies
1
Views
1K
  • · Replies 2 ·
Replies
2
Views
3K
  • · Replies 3 ·
Replies
3
Views
2K