Finding least number of triangles by degree density and limit value of K4 clique(by Erdos-Simonovits-Stone Theorem )

52 Views Asked by At

In the problem of finding the least number of triangles in graph with 'n' vertices and 'm' edges, can this formula work to find the lower bound?

$ ≥ (value of limit for K-4 clique)×{(Sum of degree of all vertices)/(Number of vertices)}×(Number of vertices-Number of maximum vertices in a triangle free graphs)$

Here I took value of limit for K-4 clique because in a complete bipartite graph when we add an edge to both partitions, we get a K4 clique with four triangles. So trying to restrict the formation of K4 clique, I took the limiting value of K4 clique from Erdos-Simonovits-Stone Theorem. I took ${(Sum of degree of all vertices)/(Number of vertices)}$ to find the average density of degree of each vertex and multiplied it by the number of left vertices after forming triangle free graph of most number of edges possible.

Does it makes sense as by putting the values, we get the correct lower bound possible? Can this be generalised or modified for making more sense? (Pardon for bad presentation)