Mantel's Theorem

Mantel's theorem (Mantel 1907) states that every triangle-free graph on graph vertices has edge count satisfying

Here and denote the floor function and ceiling function, respectively. Equivalently, every graph on graph vertices with more than graph edges contains a triangle.

The bound is attained uniquely up to graph isomorphism by the complete bipartite graph , whose two parts differ in size by at most one (Bollobás 1998). In the notation of extremal graph theory, if denotes the maximum number of graph edges in a graph on graph vertices containing no subgraph isomorphic to , then

where is the complete graph on three graph vertices.

Mantel's theorem is the case of Turán's theorem, and the extremal graph is the Turán graph .