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

  • Thread starter MathematicalPhysicist
  • Start date
  • Tags
    Graph
In summary, the conversation discussed proving the existence of two triangles with a common edge in a graph G with 1000 vertices and 250,001 edges. The goal was to show that the set of graphs without the specified triangles, denoted by F_1, is a subset of the set of graphs without any triangles, denoted by F_2. It was reasoned that if K_3 (a triangle) is not a subgraph of G, then H (the graph with two triangles and a common edge) cannot be a subgraph either. However, it was questioned whether F_2 is actually a subset of F_1 and not the other way around.
  • #1
MathematicalPhysicist
Gold Member
4,699
371
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?
 
Last edited:
Physics news on Phys.org
  • #2
Anyone?
Where have I gone wrong here?

Cheers!
 

1. How do you determine if there are two triangles with a common edge in a 1000-vertex graph?

The first step is to visually examine the graph and identify any potential triangles with a common edge. This can be done by tracing the edges and identifying any intersecting paths. Additionally, mathematical algorithms and tools can be used to analyze the graph and determine if there are any triangles with a common edge.

2. Is it possible for a 1000-vertex graph to have multiple triangles with a common edge?

Yes, it is possible for a 1000-vertex graph to have multiple triangles with a common edge. In fact, the number of distinct triangles in a graph can be much larger than the number of vertices. Therefore, it is important to carefully analyze the graph and consider all possible combinations of triangles with a common edge.

3. Can you prove the existence of two triangles with a common edge in a 1000-vertex graph?

Yes, it is possible to prove the existence of two triangles with a common edge in a 1000-vertex graph. This can be done by providing a mathematical proof or by visually identifying and tracing the triangles in the graph. However, proving the existence of all possible triangles with a common edge in a 1000-vertex graph may be more challenging and time-consuming.

4. How important is it to prove the existence of two triangles with a common edge in a 1000-vertex graph?

The importance of proving the existence of two triangles with a common edge in a 1000-vertex graph depends on the specific context and purpose of the analysis. In some cases, it may be crucial for understanding the structure of the graph or for solving a specific problem. In other cases, it may not be as significant and simply serve as an interesting observation.

5. Are there any practical applications of proving the existence of two triangles with a common edge in a 1000-vertex graph?

There are many potential practical applications of proving the existence of two triangles with a common edge in a 1000-vertex graph. This information can be used in network analysis, social network analysis, graph theory, and other fields. It can also be used to improve algorithms and strategies for solving problems on large graphs, such as finding the shortest path or identifying clusters of nodes.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
774
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
4
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
Back
Top