Bollobás-Erdős Triangle Degree-Sum Conjecture

The Bollobás-Erdős triangle degree-sum conjecture asserts that every sufficiently large simple graph with vertices and more than edges contains a graph triangle whose vertex degrees sum to at least (Erdős 1993). It is the proposed asymptotic lower bound in Erdős problem 1033, rather than the whole problem of determining the best guaranteed degree sum.

A counterexample is obtained by replacing the five vertices of a butterfly graph by independent sets and retaining selected edges between parts corresponding to adjacent vertices. The construction was reported by rickyc (2026), who attributed it to GPT-5.5 Pro, and its parameters were improved by Wouter CvB (2026).

An explicit version formalized by ukniusanqian-alt has vertices and edges, with vertex degree sum on every graph triangle, for each positive integer (Palomar Registry 2026). Since and , this disproves the proposed asymptotic bound. Palomar Registry (2026) records kernel acceptance of this rational construction. The sharper optimized coefficient in Wouter CvB's note is a separate assertion. The optimal graph triangle degree-sum bound remains undetermined.