How many edges are needed if at least there is an edge among any 3 vertices?

560 Views Asked by At

In a simple graph, how many edges are needed if at least there is an edge among any 3 vertices?

1

There are 1 best solutions below

0
On BEST ANSWER

If a graph has at least one edge among any $3$ vertices, then the complementary graph contains no triangle, and vice versa. What is the most edges an $n$-vertex (simple) graph can have without containing a triangle? [*] Subtract from $\binom n2$.

[*] Hint: Mantel, Turán.