A LIMIT ON NETWORKS, NOW PROVED FOR EVERY SIZE
Take a few points and join some pairs of them by lines. Mathematicians call this a graph: the points are its vertices, the lines its edges, and the distance between two vertices is the fewest edges needed to walk from one to the other. Now add two rules. Every pair of vertices must be at distance at most 2 — joined directly, or through a common neighbour. And no edge may be spare: delete any single one, and some pair ends up more than two steps apart. Such a graph is called diameter-2-critical. How many edges can it have?
Mantel’s ceiling, and a bolder guess
In 1907, Mantel proved that a graph on n vertices with no triangle — no three vertices all joined to one another — has at most ⌊n²/4⌋ edges: n squared divided by four, rounded down to a whole number. Only one graph reaches that ceiling, the balanced complete bipartite graph: two groups as equal in size as possible, every vertex of one joined to every vertex of the other, no edge inside a group.
Every triangle-free graph that cannot take one more edge without creating a triangle is diameter-2-critical. The reverse fails: some diameter-2-critical graphs contain triangles.
A diameter-2-critical graph with 7 vertices and 9 edges, containing the triangle v1v3v5. Deleting v1v3 destroys the only two-step route between v2 and v3; deleting an edge outside the triangle leaves its ends with no two-step route. — Figure 1, Das & Fox (2026), arXiv:2610.39032.
The guess was that triangles buy nothing: a diameter-2-critical graph on n vertices still has at most ⌊n²/4⌋ edges, and the balanced complete bipartite graph is still the only one to reach it. Mantel’s theorem would follow as a special case. For the 7 vertices of the figure, the ceiling is 12 edges.
A tower of 2’s
According to Erdős, as reported by Zoltán Füredi, the question goes back to work by Ore in the 1960s. Ján Plesník stated the edge bound as a conjecture in 1975; Murty and Simon proposed it independently and added that the balanced complete bipartite graph is the only extreme case — hence the Murty–Simon conjecture. In the 1970s and 1980s, bounds of the form c·n² crept down, with c ever closer to 1/4.
In 1992, Füredi proved the conjecture for every n large enough, with regularity methods — very general tools, derived from Szemerédi’s regularity lemma, whose guarantees only kick in for gigantic graphs. Hence the price, the starting size: n had to be at least a tower of 2’s of height roughly 10¹⁴, that is, 2 to the power 2 to the power 2…, worked out from the top down — each 2 raised to the power of everything above it — with about 10¹⁴ twos in the stack. Below that size, only special families of graphs had been settled.
Edges against missing edges
The new proof, by Sanjana Das and Jacob Fox of Stanford University’s Department of Mathematics, works for every n from 3 up. It uses a maximal matching: a set of edges, no two sharing a vertex, to which no further edge can be added without two of them meeting. A matching on n vertices holds at most ⌊n/2⌋ edges.
The key lemma: in a diameter-2-critical graph, for any maximal matching, the edges outside the matching are never more numerous than the non-edges — the pairs of vertices that are not joined. The rest is arithmetic. The non-edges are all the pairs minus the edges, so edges minus matching is at most pairs minus edges; gathering the edges on one side, twice the number of edges is at most the number of pairs plus the size of the matching. With 10 vertices: 45 pairs plus at most 5 matching edges makes 50, hence at most 25 edges. For every n, that sum comes to exactly twice Mantel’s ceiling.
The lemma itself is careful bookkeeping. A non-edge is critical if a single two-step route joins its ends, as for all twelve non-edges of Figure 1. The authors attach each critical non-edge to the two edges of its route and split the resulting web into connected pieces. A piece holds at most one more edge than critical non-edges, and each piece with that surplus must be paid for by a non-critical non-edge. To find them, the authors use switch exits: take an edge or critical non-edge of the piece and swap one of its ends for that end’s partner in the matching. Each non-critical non-edge is claimed at most twice, each surplus piece makes at least two claims, so there are no more surplus pieces than non-critical non-edges, which is exactly what the lemma needs.
Who found what
“This proof was mostly found by AI, specifically GPT-5.6 Sol on August 11, 2026,” the authors write in a short AI statement. The model found a full proof of the ⌊n²/4⌋ bound, which they simplified. For an even number of vertices, it also proved that the balanced complete bipartite graph is the only extreme case, relying on a fact proved by Sumner about graphs in which every maximal matching is perfect, covering every vertex.
With an odd number of vertices, no matching is perfect, and many graphs have every maximal matching miss exactly one vertex: the model’s argument could not be adapted. The authors found a different proof of the equality case, valid for every n, and wrote the paper themselves; a final pass through GPT-6 Astra led to “a few minor edits”. The paper is a preprint, not yet peer-reviewed, and it mentions no computer-checked version of the argument.
Back to 1907
If a graph ties the ceiling, the key inequality is an equality for every maximal matching. Choosing matchings cleverly, the authors show that such a graph is either a star — one vertex joined to all the others, nothing else — or has no critical non-edge at all. In a diameter-2-critical graph, every edge of a triangle lies on some critical route, so no critical non-edge means no triangle; a star has none either. A graph that ties is therefore triangle-free, and the last step is the theorem the conjecture set out to strengthen: Mantel’s result of 1907, which leaves the balanced complete bipartite graph alone at the ceiling.