Can a graph with no triangles have more than (n^2)/4 edges?

  • Thread starter Thread starter Oster
  • Start date Start date
  • Tags Tags
    Graphs Triangles
Click For Summary
SUMMARY

A graph with n vertices that contains no triangles can have at most (n^2)/4 edges. This conclusion is derived from the properties of complete graphs and the process of edge deletion to eliminate triangles. Induction is suggested as a viable method to prove this statement by incrementally increasing the number of vertices. The discussion emphasizes the importance of understanding graph theory fundamentals in this context.

PREREQUISITES
  • Graph theory fundamentals
  • Understanding of complete graphs
  • Induction as a mathematical proof technique
  • Basic knowledge of edge properties in graphs
NEXT STEPS
  • Study the properties of complete graphs and their edge counts
  • Learn about induction proofs in mathematics
  • Explore the concept of triangle-free graphs
  • Research extremal graph theory and its applications
USEFUL FOR

Mathematicians, computer scientists, and students studying graph theory or combinatorial optimization will benefit from this discussion.

Oster
Messages
84
Reaction score
0
1. Prove that a graph with n vertices that has no triangles has at most (n^2)/4 edges.



2.



3. Um so i was thinking maybe you start off with a complete graph and then keep deleting edges so as to remove the triangles within it or something? Or maybe by induction?
 
Physics news on Phys.org
Hi Oster! :smile:

Try induction (increasing the number of vertices by 1). :wink:
 

Similar threads

Prove the decomposition of a graph w/ even edges produce a 2-path set
  • · Replies 1 ·
Replies
1
Views
2K
Strong Induction, Tangled Graph
  • · Replies 3 ·
Replies
3
Views
3K
Proving a formula for # of edges
  • · Replies 8 ·
Replies
8
Views
2K
Prove that there exists a graph with these points such that....
  • · Replies 2 ·
Replies
2
Views
2K
Person i belongs to a clique iff ith diagonal entry of B^3 is positive
  • · Replies 9 ·
Replies
9
Views
2K
Proving uniqueness of almost irregular graphs with equal degrees for n=2k
  • · Replies 3 ·
Replies
3
Views
3K
Can Any Finite Graph Have Vertices with Unique Edge Counts?
  • · Replies 9 ·
Replies
9
Views
3K
Proving # Equilateral Triangles on Sphere
  • · Replies 2 ·
Replies
2
Views
2K
Euler circuit in a directed multigraph
  • · Replies 2 ·
Replies
2
Views
5K
Proving Cut Vertices in Simple Graphs
  • · Replies 2 ·
Replies
2
Views
2K