Sufficient condition for graph to have triangle

Question

I need a sufficient condition for graph to have triangle (exists $3$ vertices, each $2$ of them are connected by edge). I think it should be number of edges or the degree for vertices but didn't find any exact formula.

Answer 1

The following is known as Mantel's theorem and is what you are looking for.

Mantel's theorem: If $G$ has more than $\lfloor n/2 \rfloor (n- \lfloor n/2 \rfloor)$ edges, then $G$ always has a triangle.

Let $K(n)$ denote the maximum number of edges that a simple triangle free graph can have. To prove Turan, we need to show that it is the upper bound, since the bipartite graph gives the lower bound. Note that we have $K(1) = 0, K(2) = 1, K(3) = 2$.

---

Induction: Consider an edge and the two vertices incident on this edge. Consider the remaining $n-2$ vertices. Each of these $n-2$ vertices can be connected to at-most only one of the two left out vertices, else we will have a triangle. Hence, we get that $$K(n) \leq K(n-2) + (n-2) + 1 = K(n-2) + (n-1) \implies K(n) \leq \lfloor n/2 \rfloor (n- \lfloor n/2 \rfloor) \text{ edge}$$

---

There exists a more general form of Mantel's theorem, known as Turan's theorem, which gives the minimum number of edges in a graph that ensures that the graph always has a complete sub-graph on $r+1$ vertices. The wiki link gives more details.