Mantel's Theorem

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

(1)

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

(2)

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 .

A two-colored extension allows simple graphs on the same -element vertex set. Regard an graph edge of as a copy of color , so a shared graph edge has several colored copies. If no choice of three copies forming a triangle uses exactly two colors, then

(3)

Equality holds iff all are the same complete bipartite graph with a common bipartition (Wang et al. 2026, pp. 3-4).