Extremal Graphs Maximizing Non-Triangular Edges

Definitions and mathematical statement

Use the conventional interpretation that a graph is finite, simple, and undirected; these conventions are implicit rather than explicit in the supplied record. An edge of a graph is nontriangular if it belongs to no triangle. Write \[ q(H)=\left|\{uv\in E(H):\text{there is no }w\in V(H)\setminus\{u,v\}\text{ with }uw,vw\in E(H)\}\right|. \] For nonnegative integers $a,b,c$, let $G(a,b,c)$ have a vertex partition $A\sqcup B\sqcup C$, where $|A|=a$, $|B|=b$, and $|C|=c$. The set $A$ induces a clique, $B$ and $C$ are independent, every vertex of $B$ is adjacent to every vertex of $A\cup C$, and there are no edges between $A$ and $C$. Thus \[ |E(G(a,b,c))|=\binom{a}{2}+ab+bc. \] Conjecture (feasible-parameter formulation). For every pair of integers $n,e$ with $n\geq 0$ and $0\leq e\leq\binom{n}{2}$, there exist nonnegative integers $a,b,c$ such that \[ a+b+c=n,\qquad \binom{a}{2}+ab+bc\geq e, \] and, for every graph $H$ with $|V(H)|=n$ and $|E(H)|\geq e$, \[ q(H)\leq q(G(a,b,c)). \] The source says "for every $n$ and $e$" without specifying their ranges. The displayed ranges make the optimization feasible under the graph conventions above; including $n=0$ uses the empty-graph convention. The threshold is at least $e$ edges, not exactly $e$ edges.

The supplied curation labels the problem partially solved and reports a sufficiently-large-$n$ result of Gruslys--Letzter while retaining the unrestricted all-$n$ formulation as open. This is a supplied literature assessment, not an independently verified theorem or status determination.

Short English statement

For every feasible vertex count and edge threshold, the conjecture asks whether some graph of the specified three-part form maximizes the number of edges lying in no triangle among all graphs with that vertex count and at least that many edges. The supplied dated curation reports a result for sufficiently large vertex counts and leaves the all-size formulation open.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30003138$, title "Extremal Graphs Maximizing Non-Triangular Edges," source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. The proposed year is recorded as 2016; no individual proposer is supplied.
• Supplied report citation: Combinatorics and Probability (2017), Oberwolfach Reports, pp. 1189--1257, DOI 10.4171/owr/2016/22. https://doi.org/10.4171/owr/2016/22. The record describes these reports as documenting workshop discussions and open problems.
• Gruslys--Letzter, Minimising triangular edges. https://arxiv.org/abs/1605.00528.
• Letzter, described in the supplied record as a survey of extremal triangular-edge problems. https://shohamlet.github.io/papers/triangular-edges.pdf.
• Literature assessment dated 2026-08-21: the supplied curation reports that Gruslys--Letzter prove the exact structural conjecture for sufficiently large $n$, and that later discussion explicitly leaves the version without a large-$n$ assumption open. This is supplied dated curation derived from the OWR collection, not independently verified here.
• The registry labels the statement corrected_verified and states that it was checked against the official Oberwolfach report. This verification claim is supplied metadata, not a verification performed for this draft.