Erdős problem 1033 — live-page audit and exact small cases

Access date: 2026-07-28 UTC.

Claim labels used below:

• (a) elementary-rigorous
• (b) rigorous modulo a named theorem
• (c) plausible/structural-unverified
• (d) computational-only

0. Mandatory live-page gate

I fetched both the live problem page

and its discussion thread

with a Bright Data browser, not datacenter curl. I also inspected the

rendered status/marker table, followed the bibliography controls, and saved

full-page screenshots during the run.

Verbatim live statement

> Let \(h(n)\) be such that every graph on \(n\) vertices with \(>n^2/4\)

> many edges contains a triangle whose vertices have degrees summing to at

> least \(h(n)\). Estimate \(h(n)\). In particular, is it true that

> \[ > h(n)\geq (2(\sqrt{3}-1)-o(1))n? > \]

The citation header is #1033: [Er82e,p.71][Er93,p.344].

Current status and all activity markers

The rendered page says:

• Status: OPEN.
• Last main-page edit: 03 April 2026.
• Comments: 5.
• Claimed proofs: 0.
• Likes this problem: None.
• Interested in collaborating: None.
• Currently working on this problem: None.
• Looks difficult: JohanLand.
• Looks tractable: None.
• Results could be formalisable: None.
• Working on formalising the results: None.

Thus neither the claimed-proof nor current-worker stop condition fires. The

comments do say that the highlighted proposed asymptotic lower bound has been

disproved, but they explicitly distinguish that subquestion from the still-open

request to estimate \(h(n)\).

All five comments

In oldest-first order:

1. rickyc, 16:51 on 27 Jun 2026: links a public ChatGPT conversation and

says GPT-5.5 Pro claims an explicit construction disproving the proposed

lower bound.

2. JohanLand, 19:52 on 26 Jul 2026: says the construction appears to hold

up, so the displayed lower-bound conjecture is false; records

\[ \frac{21}{16}n\leq h(n)\leq 1.46393n+O(1), \]

and stresses that this does not resolve the estimation problem.

3. rickyc, 21:52 on 26 Jul 2026: expects other constructions may improve

the bound and notes that there is no candidate for the true constant.

4. Wouter CvB, 14:38 on 27 Jul 2026: links

a three-page construction note

optimizing the same five-part butterfly blow-up to

\(1.463877226\ldots\), a root of a degree-seven polynomial. The comment

says connected support graphs on at most seven vertices were tried; the

PDF says, less precisely, that its experiments included all graphs on at

most eight vertices. Neither exhaustive-search assertion comes with code

or a certificate, so I do not use it as a theorem.

5. rickyc, 15:11 on 27 Jul 2026: says GPT confirms the refinement and

suggests that further small constant improvements may be meaningful.

The page itself warns that comments are unverified. The linked PDF downloaded

in this run had SHA-256

f42a5ecece0979af67806fc1f5d8d7e9d47dfc441b0a95e78398c6e90af487fb.

1. Ground truth and literature check

The main page records

It attributes the upper construction to Erdős--Laskar and the lower bound to

Fan. It also explains the classical upper construction: start with a complete

bipartite graph with parts \(k+l=n\), add

\(\lfloor n^2/4\rfloor+1-kl\) triangle-free, nearly regular edges inside the

\(k\)-part, and optimize at \(k/n=1/\sqrt3\).

I checked the following primary records rather than relying on paper titles

from secondary search results:

• The Rényi Institute scan of Erdős,

Some of my favourite problems which recently have been solved,

exists. Page 71 discusses the triangle degree-sum problem. **(a:

bibliographic/content check)**

• The publisher record for Erdős,

Some of my favorite solved and unsolved problems in graph theory,

verifies Quaestiones Mathematicae 16 (1993), 333–350, DOI

10.1080/16073606.1993.9631741. Page 344 is paywalled, so I verified the

record but did not pretend to inspect that page.

• The Erdős archive scan of Erdős--Laskar,

A note on the size of a chordal subgraph,

exists as Congressus Numerantium 48 (1985), 81–86.

• Fan's publisher record,

Degree sum for a triangle in a graph,

exists as Journal of Graph Theory 12 (1988), 249–263. Its abstract

defines the two-parameter extremal function \(f(n,e)\), states

\(f(n,e)\geq 21e/(4n)\), and records the relevant upper construction.

• Bollobás--Nikiforov,

The sum of degrees in cliques,

is genuinely arXiv:math/0410218 and later appeared in *Electronic Journal

of Combinatorics* 12 (2005), N21. Its near-\(t_r(n)\) theorem is the

higher-density general result quoted on the page; it does not settle the

near-Mantel regime here.

Exact-title, formula, DOI, Erdős-archive, and arXiv searches found no later

primary paper specifically improving Fan's near-\(n^2/4\) lower bound. This

is an honest search miss, not a claim that no such paper exists.

The linked July 2026 butterfly note sets

and uses the root

The companion checker independently brackets a sign-changing root, evaluates

all displayed density formulas at 80-decimal precision, verifies that the five

part weights sum to one, that both partial densities lie in \((0,1)\), that

the limiting edge density is exactly \(1/4\) to the computed precision, and

that the two possible triangle types both have normalized degree sum \(y_0\).

That is an arithmetic/support check (d), not certification of the PDF's

claim that this is the global butterfly optimum.

2. A finite reduction

For a graph \(G\), define

Equivalently,

Let

Fixed-edge lemma. (b, modulo Mantel's theorem)

Proof. A graph with at least \(m_0(n)\) edges has a spanning subgraph

\(H\) with exactly \(m_0(n)\) edges (take \(H=G\) in the equality case).

Every triangle of \(H\) is a triangle of

\(G\), and \(d_H(v)\leq d_G(v)\) for every vertex, so \(s(H)\leq s(G)\).

Mantel's theorem ensures that \(H\) has a triangle. The reverse inequality is

immediate because every graph with \(m_0(n)\) edges is allowed. \(\square\)

This reduction makes each fixed \(n\) a finite, exact computation.

3. Exact computation for \(3\leq n\leq10\)

Method

For each \(n\), I generated every nonisomorphic simple graph with exactly

\(m_0(n)\) edges using nauty-geng 2.8.8. A separately written graph6 decoder

then:

1. reconstructed the adjacency bitsets;

2. recomputed the edge count and every vertex degree;

3. enumerated every triangle;

4. evaluated \(s(G)\); and

5. retained the minimum and the number of isomorphism classes attaining it.

The official nauty/Traces page

documents geng as a generator of nonisomorphic graphs. Reliance on that

software is why the equality table is labelled (d).

As an independent cross-check, the verifier also enumerates *all labeled edge

subsets from scratch* for \(3\leq n\leq7\), without nauty. The largest such

second search checks all

\(\binom{21}{13}=203{,}490\) labeled graphs. Both implementations agree.

Result

Exact finite table (d):

| \(n\) | \(m_0(n)\) | \(h(n)\) | nonisomorphic graphs checked | nonisomorphic minimizers | one upper certificate |

|---:|---:|---:|---:|---:|:---|

| 3 | 3 | 6 | 1 | 1 | \(K_3\) |

| 4 | 5 | 8 | 1 | 1 | \(K_{2,2}+K_2\) in the 2-side |

| 5 | 7 | 9 | 4 | 1 | \(K_{3,2}+K_2\) in the 3-side |

| 6 | 10 | 10 | 15 | 1 | \(K_{4,2}+2K_2\) in the 4-side |

| 7 | 13 | 12 | 97 | 11 | \(K_{5,2}+(P_3\sqcup K_2)\) in the 5-side |

| 8 | 17 | 13 | 980 | 6 | \(K_{5,3}+(2K_2\sqcup K_1)\) in the 5-side |

| 9 | 21 | 14 | 21,933 | 3 | \(K_{6,3}+3K_2\) in the 6-side |

| 10 | 26 | 16 | 828,728 | 259 | \(K_{6,4}+(2K_2\sqcup2K_1)\) in the 6-side |

Here “add \(H\) in the \(a\)-side” means start with \(K_{a,b}\) and insert the

edges of \(H\) among those \(a\) vertices. The edge counts and maximum

triangle degree sums of all eight displayed certificates are direct finite

checks (a). The matching lower bounds are the exhaustive computation

(d).

The independent labeled enumeration produced:

| \(n\) | labeled graphs checked | labeled minimizers | minimum |

|---:|---:|---:|---:|

| 3 | 1 | 1 | 6 |

| 4 | 6 | 6 | 8 |

| 5 | 120 | 30 | 9 |

| 6 | 3,003 | 45 | 10 |

| 7 | 203,490 | 14,700 | 12 |

No asymptotic conclusion is drawn from this finite list.

4. Reproduction and independent checker

The complete checker is

runs/erdos1033_wave8a_reverify.py, SHA-256

593fd9d88aae05c3ebad60638c3d72e6c11df8b8872d7fbe9aa2f3cdb1fbc577.

Run:

python runs/erdos1033_wave8a_reverify.py

On this VM (Python 3.12.3, nauty 2.8.8+ds-5), the full run took about 26

seconds and ended:

nauty n=10: m=26, h=16, graphs=828728, minimizers=259
nauty enumeration: PASS
independent enumeration agreement: PASS (n=3..7)
ALL CHECKS PASSED

The nauty-independent portion can be run with:

python runs/erdos1033_wave8a_reverify.py --skip-nauty

It verifies all explicit certificates, the posted butterfly arithmetic, and

the complete labeled searches through \(n=7\).

The core scoring rule is deliberately simple:

degrees = tuple(mask.bit_count() for mask in adj)
maximum = -1
for a in range(n - 2):
    for b in range(a + 1, n - 1):
        if not ((adj[a] >> b) & 1):
            continue
        common = adj[a] & adj[b] & ~((1 << (b + 1)) - 1)
        while common:
            bit = common & -common
            c = bit.bit_length() - 1
            maximum = max(maximum, degrees[a] + degrees[b] + degrees[c])
            common ^= bit

The standalone file contains the graph generator invocation, graph6 decoder,

direct labeled enumerator, certificate construction, assertions, and

high-precision butterfly check. Expected values appear only as

post-computation assertions; the searches recompute each result before making

that comparison.

5. What remains and the precise asymptotic wall

The best live construction claim is currently approximately

whereas Fan gives

The exact finite table does not bridge this uniform gap.

A natural graphon formulation has degree function

and asks to control the essential supremum of

over triangle-support triples. The missing lemma is a **uniform structural

or lower-bound theorem** showing that every graph (or limiting graphon) of

edge density just above \(1/4\) must contain such a triple with degree sum at

least a proposed constant. Ordinary Mantel stability does not supply this:

the objective depends on where triangle-support edges are positive and is not

continuous under the usual coarse convergence when small edge densities are

turned on or off.

Numerical optimization of a fixed finite support graph cannot repair that

uniformity gap. It is a nonconvex search, support changes are discontinuous,

and checking support graphs on at most seven or eight vertices does not reduce

arbitrary graphs or graphons to that finite list. A proof would need either:

1. a stability/classification theorem reducing all near-extremizers to a

certified finite family of weighted templates; or

2. a new global inequality improving Fan's \(21/16\) lower constant.

I found neither lemma. Therefore this report claims the exact small cases,

not a solution of the asymptotic problem and not global optimality of the

butterfly construction.

PARTIAL: Exhaustive computation gives h(3..10) = 6,8,9,10,12,13,14,16 with explicit certificates and an independent labeled cross-check through n=7; the asymptotic constant remains open.