In a simple graph, how many edges are needed if at least there is an edge among any 3 vertices?
2026-05-05 10:17:03.1777976223
How many edges are needed if at least there is an edge among any 3 vertices?
560 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
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.