1 Introduction to Mantel’s theorem

1.1 Problem setting: extremal edges in forbidden-subgraph graphs

Mantel’s theorem is an archetypal result in extremal graph theory. It asks a basic optimization question: among all simple graphs on a fixed number of vertices, what is the largest number of edges a graph can have while avoiding a particular forbidden subgraph? In this case, the forbidden structure is a triangle.

The theorem not only gives the maximum edge count, but also identifies the form of graphs that achieve it, illustrating a recurring theme in extremal combinatorics: extremal graphs tend to be highly structured even when the constraint is only local (here, a triangle).

1.2 Triangle-free graphs and the \(K_3\)-free condition

A graph is triangle-free if it contains no subgraph isomorphic to \(K_3\), the complete graph on three vertices. Equivalently, there do not exist three vertices that are pairwise adjacent. Mantel’s theorem determines the maximum possible number of edges in an \(n\)-vertex triangle-free graph.

1.3 Historical context and relationship to extremal graph theory

Mantel’s theorem was established as an early cornerstone of the subject and helped motivate systematic study of “forbidden configuration” problems. It is widely presented as the \(r=3\) instance of Turán’s theorem, which generalizes the maximum-edge question from forbidding triangles to forbidding larger complete graphs \(K_r\).

Conceptually, Mantel’s theorem demonstrates how restricting small patterns can enforce global density limitations.

2 Statement of the theorem

2.1 Edge upper bound for triangle-free graphs

Mantel’s theorem states that if \(G\) is a triangle-free simple graph on \(n\) vertices, then \[ e(G)\le \left\lfloor \frac{n^2}{4}\right\rfloor, \] where \(e(G)\) denotes the number of edges.

This bound is tight: there exist triangle-free graphs whose edge counts reach the stated maximum.

2.1.1 Deriving the formula \(\left\lfloor \frac{n^2}{4}\right\rfloor\)

Let the vertices be split into two parts of sizes \(a\) and \(b\) with \(a+b=n\). A complete bipartite graph \(K_{a,b}\) has exactly \(ab\) edges. For triangle-free constructions, this kind of graph is natural because it contains no triangles: any edge joins opposite sides, so three pairwise adjacent vertices would require three sides, which is impossible in a bipartite graph.

To maximize \(ab\) subject to \(a+b=n\), one uses the fact that \(ab\) is maximized when the parts are as equal as possible. Thus:

  • If \(n=2m\) is even, take \(a=b=m\), giving \(ab=m^2 = n^2/4\).
  • If \(n=2m+1\) is odd, take \(a=m\) and \(b=m+1\), giving \(ab=m(m+1)=\lfloor n^2/4\rfloor\).

This matches the stated upper bound, showing that \(\left\lfloor n^2/4\right\rfloor\) is the best possible number consistent with a bipartite extremal construction.

2.2 Equality (extremal) cases

2.2.1 Complete bipartite graphs as optimal constructions

The equality cases are described as follows: a triangle-free graph on \(n\) vertices achieves the maximum \(\left\lfloor n^2/4\right\rfloor\) edges if and only if it is a complete bipartite graph whose two parts have sizes as equal as possible. Concretely, it is isomorphic to:

  • \(K_{m,m}\) when \(n=2m\),
  • \(K_{m,m+1}\) (or \(K_{m+1,m}\)) when \(n=2m+1\).

2.3 Small-\(n\) examples and sanity checks

Small instances illustrate the formula.

  • \(n=1\): the graph has 0 edges; \(\lfloor 1/4\rfloor=0\).
  • \(n=2\): at most 1 edge; \(\lfloor 4/4\rfloor=1\), achieved by \(K_2\).
  • \(n=3\): a triangle is forbidden, so the maximum is 2 edges (a path of length 2). The formula gives \(\left\lfloor 9/4\right\rfloor=2\).
  • \(n=4\): maximum is 4 edges, achieved by \(K_{2,2}\). The formula gives \(\left\lfloor 16/4\right\rfloor=4\).

These checks align with the general statement.

3 Proof approaches

3.1 Proof via double counting

A common proof counts certain configurations in two ways, forcing a triangle to appear if the edge count is too large.

The key idea is to use the fact that if a graph is triangle-free, then the neighborhoods of adjacent vertices must be disjoint in a controlled way. That restriction limits how many edges can exist.

3.1.1 Counting edges across a partition and preventing triangles

One route is:

  1. Consider any triangle-free graph \(G\) and select a vertex \(v\).
  2. Let \(N(v)\) be the neighborhood of \(v\), and note that there are no edges inside \(N(v)\); otherwise an edge \(xy\) with \(x,y\in N(v)\) would form a triangle \(vxy\).
  3. Therefore, the subgraph induced by \(N(v)\) is edgeless, implying that the number of edges incident to vertices in \(N(v)\) is limited.

A more global version selects a partition related to the extremal bipartite structure and counts edges between parts. The triangle-free condition prevents certain “closing” interactions that would create triangles, and the double-counting inequalities culminate in the bound \(\lfloor n^2/4\rfloor\).

3.2 Proof using convexity/averaging ideas

Another perspective is to show that among graphs with fixed average degree (or fixed edge count), the triangle-free condition imposes constraints that are optimized by making degrees as equal as possible and pushing the graph toward bipartite symmetry.

3.2.1 Symmetrization intuition for extremal graphs

Symmetrization techniques formalize an intuitive message: if an extremal triangle-free graph has an irregular structure, one can often “smooth” it (by replacing certain adjacency patterns) without decreasing the edge count and while preserving triangle-freeness. Repeating such operations drives the graph toward a bipartite form with two parts of nearly equal sizes.

Even when presented only as an intuition, this method explains why extremal examples have the nearly balanced complete bipartite form rather than an arbitrary triangle-free structure.

3.3 Proof via contradiction from maximality

3.3.1 Why any deviation from bipartite structure reduces edges

A typical contradiction argument assumes a triangle-free graph \(G\) with more than \(\lfloor n^2/4\rfloor\) edges exists, or assumes a maximal-edge triangle-free graph that is not complete bipartite in the required balanced manner.

  • If \(G\) has too many edges, its density forces configurations that necessarily create a triangle.
  • If \(G\) is extremal but not bipartite complete between two parts, one can often identify a local structural defect (for example, missing edges across a candidate partition) and show that inserting them would not introduce triangles—contradicting maximality—or that other missing edges elsewhere must exist, reducing total edge count.

This approach emphasizes the rigidity of the extremal structure: to be edge-maximal under triangle-freeness, the graph must essentially coincide with the bipartite construction.

4 Extremal graph structure

4.1 The role of bipartite partitions

The maximal triangle-free graphs are complete bipartite graphs with the partition balanced as evenly as possible. The bipartition eliminates triangles because all edges run between the two sides.

From a structural standpoint, Mantel’s theorem suggests that the triangle-free condition is best satisfied by maximizing the number of cross edges between two large groups while forbidding any internal edges in either group.

4.2 Uniqueness up to isomorphism (for maximal cases)

For a fixed \(n\), equality in Mantel’s bound pins down the graph’s structure up to isomorphism:

  • when \(n\) is even, the extremal graph is unique up to relabeling: \(K_{n/2,n/2}\);
  • when \(n\) is odd, there are two sides of sizes \(\lfloor n/2\rfloor\) and \(\lceil n/2\rceil\), and swapping the sides gives an isomorphic graph.

Thus, the theorem provides both a numeric optimum and a precise description of achieving configurations.

4.3 Stability intuition: near-extremal graphs resemble bipartite graphs

Even when a triangle-free graph does not attain the maximum exactly, it often cannot be far from the bipartite extremal family. The density required to get close to \(\lfloor n^2/4\rfloor\) tends to force the same “two-cluster” organization: most edges run between two large vertex classes, with only limited deviations.

This stability phenomenon is a broader motif in extremal graph theory, where extremal bounds are accompanied by structural closeness statements.

5 Connections and generalizations

5.1 Turán’s theorem (general \(K_r\)-free case)

Turán’s theorem generalizes Mantel’s result. It determines the maximum number of edges in an \(n\)-vertex graph that does not contain \(K_r\) as a subgraph. Instead of a bipartition, the extremal construction uses an \(r-1\) partite structure with parts as equal in size as possible.

The guiding principle remains the same: forbidding a complete graph of fixed size forces the edge density to spread into a controlled multipartite arrangement.

5.2 Specialization of Turán to \(r=3\)

Setting \(r=3\) in Turán’s theorem yields exactly Mantel’s theorem. In this case, the extremal graph is complete bipartite (which is the same as having 2 parts, because \(r-1=2\)). The edge count becomes \(\left\lfloor n^2/4\right\rfloor\), matching the triangle-free bound.

Ramsey theory studies thresholds where complete substructures become unavoidable. While Mantel’s theorem is an extremal (maximum edges under prohibition) statement rather than a Ramsey (guarantee of existence) statement, it is part of the same landscape: both themes relate how large graphs must “contain” certain patterns or else be constrained in structure.

In particular, Mantel’s theorem can be viewed as the extremal counterpart of the idea that sufficiently dense graphs tend to create triangles.

6.1 Bounds in combinatorial design and incidence settings

Extremal estimates for forbidden subgraphs feed into combinatorial design questions, especially those involving incidence graphs where triangles correspond to certain repeated incidence patterns. Bounding triangles can translate into controlling configurations in systems such as block designs or finite geometry incidence structures.

In many such applications, the goal is not to classify the entire graph but to obtain tight inequalities on parameters that would otherwise be difficult to estimate directly.

6.2 Connections to graph coloring and independence number

Triangle-free graphs have constraints that interact with coloring and independent sets. For example, in a triangle-free graph, the complement graph’s structure influences independent sets in the original graph, and maximum edge bounds indirectly affect how large independent sets can be forced.

While Mantel’s theorem itself is not a coloring theorem, its extremal edge statement provides input for subsequent results bounding chromatic numbers or independence numbers in related families.

6.3 Benchmarking extremal methods and techniques

Mantel’s theorem is frequently used as a benchmark in proofs: it is simple enough to be taught early but rich enough to illustrate powerful tools such as double counting, averaging, and extremal-structure reasoning. Many later theorems in extremal graph theory can be seen as sophisticated analogues of the same core logic: convert a prohibition into a quantitative bound and then determine the maximizing configuration.

7 Worked examples

7.1 Computing Mantel bounds for given \(n\)

To compute the Mantel maximum for triangle-free graphs on \(n\) vertices, evaluate \(\left\lfloor n^2/4\right\rfloor\).

Examples:

  • \(n=10\): \(\lfloor 100/4\rfloor=25\).
  • \(n=11\): \(\lfloor 121/4\rfloor=30\).
  • \(n=12\): \(\lfloor 144/4\rfloor=36\).

7.2 Verifying extremal constructions for specific \(n\)

To build an extremal graph achieving the bound:

  • For even \(n=2m\), take \(K_{m,m}\), which has \(m^2 = n^2/4\) edges.
  • For odd \(n=2m+1\), take \(K_{m,m+1}\), which has \(m(m+1)=\lfloor n^2/4\rfloor\) edges.

Check triangle-freeness: every edge goes between the two parts, so any three vertices cannot be pairwise adjacent; hence no \(K_3\) appears.

7.3 Constructing maximal triangle-free graphs explicitly

Example: \(n=7\). Here \(n=2\cdot 3+1\), so the maximum is \[ \left\lfloor \frac{7^2}{4}\right\rfloor=\left\lfloor \frac{49}{4}\right\rfloor=12. \] Construct the extremal graph as \(K_{3,4}\):

  • partition vertices into a set of 3 and a set of 4;
  • connect every vertex in the 3-set to every vertex in the 4-set;
  • add no edges within either set.

The resulting graph has \(3\cdot 4=12\) edges and is triangle-free by bipartiteness.