Checking Mantel Bounds on Small Graphs

What a Small-Graph Check Can Show

Mantel’s theorem gives a sharp upper bound on the number of edges in a triangle-free graph. On a small vertex set, the bound is useful not only as a theorem to quote but also as a quantity to check: count the edges of a particular graph, verify that it has no triangle, and compare its count with the bound. A graph that reaches the bound is an extremal example; one that falls short is still triangle-free, but it does not attain the maximum.

Throughout, graphs are finite and simple: there are no loops or multiple edges. A triangle is a cycle of length $3$. A graph is triangle-free if it contains no triangle. The order of $G$ is $n=|V(G)|$, and its size is $m=|E(G)|$.

Theorem (Mantel's theorem): If $G$ is a triangle-free simple graph of order $n$, then $$ |E(G)|\le \left\lfloor\frac{n^2}{4}\right\rfloor. $$ For $n\ge 1$, equality is attained by the complete bipartite graph with part sizes $\lfloor n/2\rfloor$ and $\lceil n/2\rceil$. The upper bound and its equality case were proved in the earlier material on Mantel's theorem.

The theorem applies to every finite simple triangle-free graph, whether or not it is connected. For the empty graph, $n=0$ and $m=0$, so the bound also holds: $\lfloor 0^2/4\rfloor=0$. The floor is important because the edge count is an integer. When $n$ is odd, $n^2/4$ is not an integer, and the largest allowed integer is its floor.

Why the Balanced Construction Has the Bound's Size

For disjoint vertex sets $X$ and $Y$, the complete bipartite graph $K_{a,b}$ has parts of sizes $a=|X|$ and $b=|Y|$. Its edges are exactly the pairs with one endpoint in $X$ and one in $Y$. Thus it has $ab$ edges. It is triangle-free: along any edge, a walk moves from one part to the other, so a three-edge cycle cannot return to its starting part.

Proposition: Among complete bipartite graphs on $n$ vertices, the largest edge count is $\lfloor n^2/4\rfloor$, attained when the part sizes differ by at most one.

Proof. Let the part sizes be nonnegative integers $a,b$ with $a+b=n$. The edge count is $ab$. Since a square is nonnegative, $$ (a-b)^2\ge 0. $$ Expanding and using $a+b=n$ gives $$ n^2=(a+b)^2=(a-b)^2+4ab\ge 4ab, $$ so $ab\le n^2/4$. Because $ab$ is an integer, $ab\le\lfloor n^2/4\rfloor$. Write $n=2q$ if $n$ is even. The choice $a=b=q$ gives $ab=q^2=n^2/4$. If $n=2q+1$ is odd, choose $a=q$ and $b=q+1$; then $ab=q(q+1)=(n^2-1)/4=\lfloor n^2/4\rfloor$. These choices have part sizes differing by at most one and attain the stated bound. This argument includes $n=0$, where $a=b=0$ and the edge count is zero. $\square$

This calculation gives the construction side of Mantel’s theorem: it exhibits triangle-free graphs with the claimed number of edges. Mantel’s theorem supplies the other side, showing that no triangle-free graph on the same number of vertices can have more edges. Together these statements certify that the construction is extremal.

Reference Values for Small Orders

The table lists the balanced part sizes and the corresponding bound for orders from zero through eight. Each entry in the last column is the product of the two part sizes, equivalently $\lfloor n^2/4\rfloor$.

Order $n$	Balanced part sizes	Bound $\lfloor n^2/4\rfloor$
0	0 and 0	0
1	0 and 1	0
2	1 and 1	1
3	1 and 2	2
4	2 and 2	4
5	2 and 3	6
6	3 and 3	9
7	3 and 4	12
8	4 and 4	16

For instance, at order $7$ the balanced construction has $3\cdot4=12$ edges, and the formula gives $\lfloor 7^2/4\rfloor=\lfloor49/4\rfloor=12$. The table is a quick reference, not a substitute for checking a specific graph: first verify that the graph is triangle-free, then count its edges, and only then compare its size with the appropriate bound.

Worked Example: The Five-Cycle Falls One Edge Short

Let $G$ have $V(G)=\{1,2,3,4,5\}$ and $E(G)=\{12,23,34,45,51\}$. This is a five-cycle. Check that it is triangle-free, count its edges, and compare it with Mantel’s bound.

Each vertex has exactly two neighbors: vertex $1$ is adjacent to $2,5$; vertex $2$ to $1,3$; vertex $3$ to $2,4$; vertex $4$ to $3,5$; and vertex $5$ to $4,1$. In each case the two neighbors are not adjacent to each other, so no vertex can lie in a triangle. Thus $G$ is triangle-free.

The edge list contains five edges, so $m=5$. Independently, each of the five vertices has degree $2$, and the degree sum is $5\cdot2=10$. Each edge contributes one to the degree of each of its two endpoints, so $2m=10$, giving $m=10/2=5$ again. The bound at order $5$ is $\lfloor5^2/4\rfloor=\lfloor25/4\rfloor=6$. Therefore this graph is one edge below the bound.

Check: The balanced complete bipartite graph with part sizes $2$ and $3$ has $2\cdot3=6$ edges. The five-cycle has $5$, so it is triangle-free but not extremal.

Checking an Extremal Construction Directly

When a balanced complete bipartite graph is used as a comparison, its defining structure makes both checks short. Every edge must cross between its two parts, which rules out a triangle; and every possible cross-part pair is an edge, so multiplying the part sizes counts all edges. It is still useful to verify the count independently, especially when the graph is given by an edge list rather than by its parts.

Worked Example: A Five-Vertex Graph Reaches the Bound

Let $G$ have $V(G)=\{a,b,x,y,z\}$ and $E(G)=\{ax,ay,az,bx,by,bz\}$. Its parts are $\{a,b\}$ and $\{x,y,z\}$, with every cross-part pair included.

Every edge has one endpoint in $\{a,b\}$ and one in $\{x,y,z\}$. A triangle would have to alternate between the two parts at every step, but after three steps an alternating sequence is in the opposite part from where it started. Hence no triangle exists, and $G$ is triangle-free.

There are $2\cdot3=6$ cross-part pairs, and the edge list includes all six, so $m=6$. For an independent count, $a$ and $b$ each have degree $3$, while $x,y,z$ each have degree $2$. The degree sum is $3+3+2+2+2=12$, so the number of edges is $12/2=6$. Mantel’s bound is $\lfloor5^2/4\rfloor=\lfloor25/4\rfloor=6$. Thus $G$ attains the bound.

Check: The construction and the theorem agree: the graph is triangle-free, has six edges, and no triangle-free graph on five vertices can have more than six.

Worked Example: Removing One Cross-Part Edge

Let $G$ have $V(G)=\{a,b,c,x,y,z\}$ and $E(G)=\{ax,ay,bx,by,bz,cx,cy,cz\}$. This graph has parts $\{a,b,c\}$ and $\{x,y,z\}$, with the cross-part edge $az$ omitted.

Every listed edge still goes between the two parts. Any cycle in a bipartite graph alternates between its parts; in particular, a triangle is impossible. So $G$ is triangle-free. Counting the listed edges gives $m=8$. For an independent count, the degrees of $a,b,c$ are $2,3,3$, and the degrees of $x,y,z$ are $3,3,2$. Their sum is $2+3+3+3+3+2=16$, so $m=16/2=8$.

At order $6$, Mantel’s bound is $\lfloor6^2/4\rfloor=\lfloor36/4\rfloor=9$. The full balanced graph $K_{3,3}$ has $3\cdot3=9$ edges; omitting $az$ leaves $9-1=8$. Thus this graph is triangle-free and close to the bound, but it is not extremal.

Check: The two counts agree: the edge list has eight entries, and the degree sum gives $16/2=8$. The omitted edge explains why the graph has one fewer edge than the balanced construction.

How to Read the Comparison

A small-graph check involves three separate claims, and each needs its own justification:

Order: Count the vertices to determine which bound applies.
Triangle-freeness: Verify that no three vertices have all three edges between them. For a complete bipartite construction, the two-part structure gives this immediately.
Size: Count the edges, preferably checking an edge-list count against half the degree sum.

After these checks, compare the actual edge count $m$ with $\lfloor n^2/4\rfloor$. If equality holds, the graph attains Mantel’s bound. If $m$ is smaller, the graph is not extremal, regardless of how regular or symmetric it looks. The examples show both possibilities on five vertices and a one-edge-short example on six vertices.

Common Pitfall: Rounding the Parts the Wrong Way

For odd $n$, the two parts of a balanced construction do not have equal sizes. A common incorrect calculation is to take $n=5$, split it into two parts of size $\lfloor5/2\rfloor=2$, and report $2\cdot2=4$ as the bound. This has silently accounted for only four vertices. The correct balanced sizes are $\lfloor5/2\rfloor=2$ and $\lceil5/2\rceil=3$. Their product is $2\cdot3=6$, which agrees with $\lfloor5^2/4\rfloor=\lfloor25/4\rfloor=6$.

Another mistake is to treat a large edge count as evidence of triangle-freeness. Mantel’s theorem is conditional: it bounds the edge count only after triangle-freeness has been established. In a specific graph, checking the edge count alone does not rule out a triangle. Conversely, finding that a triangle-free graph has fewer edges than the bound does not indicate an error; it means only that this graph does not attain the maximum.

Check Your Understanding

For each question, state the graph or numerical check that supports your answer.

What is Mantel’s bound for a triangle-free graph on $7$ vertices, and what balanced part sizes attain it?
Let $V(G)=\{1,2,3,4\}$ and $E(G)=\{12,23,34\}$. Is $G$ triangle-free, how many edges does it have, and how does its size compare with the bound?
Explain why a complete bipartite graph cannot contain a triangle.
A triangle-free graph on $6$ vertices has $9$ edges. What can Mantel’s theorem tell you about its edge count?
For odd order $n=2q+1$, write the balanced part sizes and their product. Explain why using two parts both of size $q$ misses a vertex.