Abstract
It is easy to assume that adding edges without forming a triangle, until none can be added, yields the graph with the most edges. This paper counts all small graphs and finds that the stuck shapes and the fullest shapes are different. No new theorem or law is claimed.
First, the most edges have a ceiling: for every $n$ from $3$ to $7$, a triangle-free graph has at most $\lfloor n^2/4\rfloor$ edges, and one edge more gave $0$ graphs (Section 2).
Second, the fullest shapes are always split in two: every triangle-free graph with exactly $\lfloor n^2/4\rfloor$ edges is a balanced complete bipartite graph; there are $10$ on $6$ vertices and $35$ on $7$, the number of ways to split into two parts (Section 2).
Third, and this is the core. Being unable to add an edge does not mean having the most: of the $211$ stuck graphs on $6$ vertices, only $10$ reach the maximum of $9$ edges, a share of $\mathbf{0.047393}$ (Section 3).
Fourth, most stop part way: on $6$ vertices, $180$, a share of $\mathbf{0.853081}$, stop at $7$ edges, and all of them are non-bipartite. On $5$ vertices, $12$ stop at the pentagon’s $5$ edges (Section 3).
Fifth, split in two is not enough without balance: the stuck complete bipartite graphs on $6$ vertices have $5$, $8$ and $9$ edges for parts $(1,5)$, $(2,4)$ and $(3,3)$, and their counts $6$, $15$ and $10$ match the numbers of ways to split (Section 3).
Sixth, the separator is whether one asks that no edge can be added (maximal) or that the edges are most numerous (maximum): a procedure that adds edges stops at a maximal graph; whether it is the maximum cannot be seen without surveying everything (Section 4).
Keywords: Mantel’s theorem, Turán’s theorem, triangle-free graph, complete bipartite graph, maximal versus maximum.
Scope (what is not claimed)
No new theorem or law is claimed: that a triangle-free graph has at most $\lfloor n^2/4\rfloor$ edges (Mantel’s theorem), that the maximum is attained by a complete bipartite graph (the first case of Turán’s theorem), and that maximal differs from maximum, are all known. No theorem is proved: we only count for $3$ to $7$ vertices. Forbidden shapes are not widened: avoiding shapes larger than a triangle, such as complete graphs on four vertices, was not counted. Size is not generalised: stuck graphs were fully counted only up to $6$ vertices, and maxima up to $7$. Relation to earlier papers: Paper 839 showed that whether a matching exists is not decided by the number of edges, only by whether some set has a smaller neighbourhood. This paper stands beside it. There matchings were counted within graphs already split in two. Here, drawing the most edges while avoiding triangles, the graph itself splits in two. What is added is counting $0$ graphs one edge above the ceiling for $3$ to $7$ vertices, measuring the share $0.047393$ of stuck graphs that reach the maximum, sorting where they stop by part sizes and bipartiteness, and placing the separator on maximal versus maximum.
1. Notation and the Question
Setting: consider graphs on $n$ labelled vertices in which no three vertices form a triangle. One with the most edges is called maximum; one to which any added edge creates a triangle is called maximal.
$$\max\{|E|:\ G\ \text{triangle-free}\}=\Bigl\lfloor \frac{n^2}{4}\Bigr\rfloor,\qquad \text{maximum}\ \Rightarrow\ \text{maximal},\quad \text{maximal}\ \not\Rightarrow\ \text{maximum}$$For $3$ to $7$ vertices, all choices of $\lfloor n^2/4\rfloor$ edges and of one more were tried. For $5$ and $6$ vertices, every graph was checked for being triangle-free and maximal.
Question: if edges are added while avoiding triangles until none can be added, is the result the graph with the most edges?
2. The Most Edges
Computation 2.1: for each $n$, triangle-free graphs with $\lfloor n^2/4\rfloor$ edges and with one more were counted.
| vertices | $\lfloor n^2/4\rfloor$ | count at that size | count one above | share of complete-graph edges |
|---|---|---|---|---|
| $3$ | $2$ | $3$ | $0$ | $0.666667$ |
| $4$ | $4$ | $3$ | $0$ | $0.666667$ |
| $5$ | $6$ | $10$ | $0$ | $0.600000$ |
| $6$ | $9$ | $10$ | $0$ | $0.600000$ |
| $7$ | $12$ | $35$ | $0$ | $0.571429$ |
Observation 2.2 the fullest shapes are always split into two balanced parts. Every triangle-free graph with $\lfloor n^2/4\rfloor$ edges was complete bipartite, for all $n$ from $3$ to $7$: the counts are the numbers of balanced two-part splits, $10$ on $6$ vertices and $35$ on $7$. Adding one edge created a triangle in every choice.
3. The Stuck Shapes
Computation 3.1: on $5$ and $6$ vertices, maximal triangle-free graphs were sorted by number of edges and by being complete bipartite.
| vertices | edges | shape | count |
|---|---|---|---|
| $5$ | $4$ | complete bipartite $(1,4)$ | $5$ |
| $5$ | $5$ | non-bipartite (pentagon) | $12$ |
| $5$ | $6$ | complete bipartite $(2,3)$ | $10$ |
| $6$ | $5$ | complete bipartite $(1,5)$ | $6$ |
| $6$ | $7$ | non-bipartite | $180$ |
| $6$ | $8$ | complete bipartite $(2,4)$ | $15$ |
| $6$ | $9$ | complete bipartite $(3,3)$ | $10$ |
Observation 3.2 this is the core. Being unable to add an edge does not mean having the most. On $6$ vertices there are $211$ stuck graphs, and only $10$, a share of $0.047393$, reach the maximum of $9$ edges: $180$, a share of $0.853081$, stop at $7$. On $5$ vertices, $12$ stop at the pentagon’s $5$ edges, a share of $0.444444$.
Observation 3.3 where a graph stops depends on its shape. A stuck bipartite graph is always complete bipartite, and the less balanced its parts, the fewer its edges: on $6$ vertices, parts $(1,5)$, $(2,4)$ and $(3,3)$ give $5$, $8$ and $9$ edges, with counts $6$, $15$ and $10$ matching the numbers of splits. All non-bipartite ones stopped at $7$.
4. The Separator
Observation 4.1 the separator is whether one asks that no edge can be added (maximal) or that the edges are most numerous (maximum). A procedure that adds edges one at a time stops at a maximal graph: whether that is the maximum cannot be seen from where it stops. On $6$ vertices only $0.047393$ of stuck graphs reach the maximum; the rest stop short of it.
Observation 4.2 placed beside Paper 839. 839 showed that whether a matching exists is not decided by the number of edges, only by whether some set has a smaller neighbourhood. There, graphs split in two were given. Here we counted that drawing the most edges while avoiding triangles makes the graph itself split into two balanced parts.
Observation 4.3 what is not said. Proofs of the theorems, avoiding shapes larger than a triangle, and $8$ or more vertices are not treated. What is shown is that the stuck shapes and the fullest shapes are different.
5. Census and Closing
- ceiling $\lfloor n^2/4\rfloor$ edges (Section 1): Mantel’s theorem.
- $0$ graphs one above (Computation 2.1): $3$ to $7$ vertices.
- all maxima complete bipartite (Observation 2.2): balanced parts.
- $35$ on $7$ vertices (Computation 2.1): number of splits.
- $211$ stuck graphs (Computation 3.1): $6$ vertices.
- reaching the maximum: $\mathbf{0.047393}$ (Observation 3.2): the core.
- stopping at $7$: $\mathbf{0.853081}$ (Observation 3.2): non-bipartite.
- $12$ stop at a pentagon (Computation 3.1): $5$ vertices.
- $(1,5)$, $(2,4)$, $(3,3)$ give $5$, $8$, $9$ (Observation 3.3): balance sets the count.
- maximal, or maximum (Observation 4.1): the separator; Paper 839.
Closing: Adding edges while avoiding triangles until none can be added does not give the most edges. Of the $211$ stuck graphs on $6$ vertices, only $10$, a share of $0.047393$, reach the maximum of $9$, and $180$ stop at $7$, because a procedure that adds edges stops at a maximal graph, and the maximum cannot be seen without surveying everything. The fullest shapes, for all $n$ from $3$ to $7$, are balanced complete bipartite graphs, and one edge more always created a triangle: split in two but unbalanced, a graph on $6$ vertices stops at $5$ or $8$ edges. Placed among the earlier papers: beside the two-part graphs that Paper 839 took as given, we placed that drawing the most edges while avoiding triangles splits the graph in two. To be honest: counts go up to $7$ vertices ($6$ for stuck graphs), and the theorems are used as known.
References
- Bollobás, B. (1998). Modern Graph Theory. Springer.
- Yamagishi, Y. (2026). Whether a Matching Exists Is Not Decided by the Number of Edges, Only by Whether Some Set Has a Smaller Neighbourhood [Paper 839]. YOI: https://www.yamagishiyuuki.com/yoi/839; DOI: 10.5281/zenodo.23015624
Reference
Yamagishi, Y. (2026). Adding Edges While Avoiding Triangles Until None Can Be Added Does Not Give the Most Edges [Paper 871]. YOI: https://www.yamagishiyuuki.com/yoi/871
ORCID: 0009-0006-8587-3450
PDF (English) · PDF (Japanese) · Date proof of the English PDF (OpenTimestamps .ots) · SHA256SUMS
The record page for this paper (in Japanese, with the PDFs in each language and the date proof): YOI 871. This paper is a preprint and has not been peer reviewed.