Local trees of triangles force quadratic order

Definitions and mathematical statement

The exact source asks whether there is a finite graph in which every edge belongs to at least two triangles and which is "locally a tree of triangles." It credits the question as solved by J. Verstraete and separately mentions Nešetřil--Rödl partial results, without giving the definition of local, a locality parameter, or a proof. Nontriviality is also implicit: an edgeless graph would satisfy the edge condition vacuously.

The supplied aid introduces an $\ell$-local formulation. An explicit working interpretation for its partial result is as follows: graphs are finite, simple and undirected; a $2$-tree is obtained from a triangle by repeatedly adjoining a new vertex joined to the endpoints of an existing edge; a partial $2$-tree is a subgraph of a $2$-tree. Require every induced subgraph on at most $\ell$ vertices to be a partial $2$-tree, and require at least one edge and \[ |N_G(u)\cap N_G(v)|\ge2\qquad(uv\in E(G)). \] The possible general existence question is then whether such a graph exists for every prescribed $\ell$. This is a specified interpretation of the aid's recovered terminology, not an independently source-verified expansion of the original sentence; local neighborhoods or other notions of triangle trees could lead to a different question.

Under this interpretation, the aid reports that for $\ell\ge3$, every connected component $H$ containing an edge has \[ \delta(H)\ge\ell, \qquad |V(H)|\ge1+\left\lceil \frac{\ell^2(\ell-1)}{2(2\ell-3)}\right\rceil. \] It attributes the first obstruction to cycles in vertex links and the $K_4$-minor obstruction for partial $2$-trees, and the order bound to averaging the $2\ell-3$ edge bound for $\ell$-vertex partial $2$-trees. The asserted order bound is sharp at $\ell=3$, witnessed by $K_4$, and at $\ell=4$, witnessed by the complete tripartite graph $K_{2,2,2}$. For $\ell=1,2$, it reports the minimum order of a nontrivial component to be four. Isolated vertices are not subject to the minimum-degree assertion.

These are necessary bounds and small-case witnesses. They do not reconstruct Verstraete's credited existence proof for arbitrary locality or resolve the ambiguity in the source's local condition. The record's solved label and the aid's partial-result label therefore have distinct scopes.

Short English statement

The source credits a solved graph-existence question but leaves its local triangle-tree condition undefined. The supplied aid gives minimum-degree and order obstructions, with exact small cases, under a partial-two-tree locality interpretation; it does not supply the credited general construction.

Sources

• Local UnsolvedMath registry, permanent ID $20000932$, source code catalogue entry; aim-combinatorics-notes.json, notes[56], tag question.
• AIM workshop "Graph Ramsey theory," "Local trees of triangles," source item 10, Overleaf source: https://www.overleaf.com/read/mnvcscjjysvg. Statement status exact; the exact question includes "Solved by J. Verstraete."
• J. Verstraete, credited solution; Nešetřil--Rödl, attributed partial results. No full authoritative paper citation, date, theorem number, or construction is supplied. No original remarks or literature field are supplied.
• Research attempt 3: partial_result, problem status at run solved, rigor label proved, novelty confidence low; registry status solved, classification SOLVED-IN-LITERATURE. Created and updated 14 August 2026. This machine-generated aid is not peer reviewed; independently verify before citation.
• Ulam AI / UnsolvedMath Contributors; CC BY 4.0.