Erdős Problem #1033

Erdős Problem 1033 --- collection record

PROVENANCE AND STATUS

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/1033.tex.

REUSED SOURCE 1

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?\] Erdős and Laskar [ErLa85] proved\[2(\sqrt{3}-1)n \geq h(n) \geq (1+c)n\]for some $c>0$. The lower bound was improved to $\frac{21}{16}n$ by Fan [Fa88]. References [ErLa85] Erdős, Paul and Laskar, Renu, A note on the size of a chordal subgraph . Congr. Numer. $1985$, 81--86. [Fa88] Fan, Genghua, Degree sum for a triangle in a graph . J. Graph Theory $1988$, 249--263.

Erdős Problem #1033 --- Solution Attempt

FORMAL RESTATEMENT. For each integer $n\ge 3$, define $h(n)$ to be the largest integer with the property: for every simple graph $G$ on $n$ vertices with $e(G) > n^2/4$, there exists a triangle $abc$ in $G$ such that \[ \deg(a)+\deg(b)+\deg(c) \ge h(n). \] The problem asks for asymptotic estimates for $h(n)$, and in particular whether \[ h(n) \ge (2(\sqrt{3}-1)-o(1))n \] as $n\to\infty$.

QUICK LITERATURE/CONTEXT CHECK. The problem statement itself records the bounds \[ (1+c)n \le h(n) \le 2(\sqrt{3}-1)n \] for some absolute $c>0$, and that the lower bound was improved to $(21/16)n$. I do not use external results beyond what is explicitly in the problem file.

ATTACK PLAN. Proof track: derive general lower bounds on the maximum triangle degree-sum in a graph with $>n^2/4$ edges. Start from averaging arguments on degrees and edges, then force a triangle via common-neighbour counting.

Disproof/upper-bound track: construct graphs with just over $n^2/4$ edges in which every triangle has small degree-sum. A natural idea: take a complete bipartite graph $K_{a,b}$ (triangle-free, $ab$ edges) with $ab$ close to $n^2/4$, and then add a sparse graph inside the smaller part to create triangles while controlling degrees.

WORK.

Lemma 1 (Edge-sum averaging forces a "large" edge, hence a "large" triangle). Let $G$ be a graph on $n$ vertices with $m=e(G)$ edges. Then there exists an edge $uv\in E(G)$ with \[ \deg(u)+\deg(v) \ge \frac{4m}{n}. \] If moreover $m>n^2/4$, then $\deg(u)+\deg(v) > n$ and hence $u,v$ have a common neighbour $w$, so $uvw$ is a triangle with \[ \deg(u)+\deg(v)+\deg(w) \ge \frac{4m}{n} + 2. \]

Proof. For each edge $uv$, define its endpoint-degree-sum $s(uv):=\deg(u)+\deg(v)$. Sum over all edges: \[ \sum_{uv\in E(G)} s(uv) = \sum_{uv\in E(G)} (\deg(u)+\deg(v)). \] Each vertex $x$ contributes $\deg(x)$ to $s(uv)$ for each incident edge $uv$, hence contributes $\deg(x)^2$ in total. Therefore \[ \sum_{uv\in E(G)} s(uv) = \sum_{x\in V(G)} \deg(x)^2. \] By Cauchy--Schwarz, \[ \sum_{x\in V} \deg(x)^2 \ge \frac{\left(\sum_x \deg(x)\right)^2}{n} = \frac{(2m)^2}{n} = \frac{4m^2}{n}. \] Divide by $m$ to get the average value of $s(uv)$ over edges: \[ \frac{1}{m}\sum_{uv\in E} s(uv) \ge \frac{4m}{n}. \] Hence some edge $uv$ satisfies $s(uv)\ge 4m/n$.

If $m>n^2/4$, then $4m/n>n$. Now $|N(u)\cup N(v)|\le n-2$, while $|N(u)|+|N(v)|=\deg(u)+\deg(v)>n$. By inclusion--exclusion, \[ |N(u)\cap N(v)| = |N(u)|+|N(v)|-|N(u)\cup N(v)| \ge (\deg(u)+\deg(v))-(n-2) > 2, \] so in particular $N(u)\cap N(v)\neq\emptyset$. Pick $w\in N(u)\cap N(v)$; then $uvw$ is a triangle. Finally, since $w$ is adjacent to both $u$ and $v$, we have $\deg(w)\ge 2$, giving \[ \deg(u)+\deg(v)+\deg(w) \ge \frac{4m}{n} + 2. \] $\square$

Consequence. Since $m>n^2/4$ implies $4m/n\ge n+\frac{4}{n}$, Lemma 1 yields the universal bound \[ h(n) \ge n+2 \qquad (n\ge 3). \] (This is very weak compared to the conjectured constant $\approx 1.464\,n$.)

Lemma 2 (An explicit construction giving the upper bound constant $2(\sqrt{3}-1)$ up to $o(n)$). For infinitely many $n$ (and in fact for all sufficiently large $n$ after rounding), there exists a graph $G$ on $n$ vertices with $e(G)>n^2/4$ such that every triangle $T$ in $G$ satisfies \[ \sum_{v\in T} \deg(v) \le \left(2(\sqrt{3}-1)+o(1)\right)n. \] In particular, this shows \[ h(n) \le 2(\sqrt{3}-1)n + o(n). \]

Construction and proof. Fix $n$ and choose an integer $a$ close to $a\approx n/\sqrt{3}$, and let $b:=n-a$. Let $A$ and $B$ be disjoint vertex sets with $|A|=a$ and $|B|=b$. Start with the complete bipartite graph between $A$ and $B$, i.e. add all $ab$ edges between $A$ and $B$. This base graph is triangle-free. Now add a graph $H$ on the vertex set $A$ only, with maximum degree at most $\Delta$ (to be chosen), and no edges inside $B$. Let $G$ be the resulting graph.

Triangle structure. Any triangle in $G$ must use exactly two vertices from $A$ and one from $B$, because: there are no edges inside $B$, and any edge inside $A$ comes from $H$. Thus every triangle consists of an $H$-edge $xy$ in $A$ together with any vertex $z\in B$ (since all $A$--$B$ edges are present).

Degree control. Every vertex in $B$ has degree exactly $a$. Every vertex $x\in A$ has degree $\deg_G(x)=b+\deg_H(x)\le b+\Delta$. Therefore any triangle $xyz$ with $x,y\in A$ and $z\in B$ satisfies \[ \deg_G(x)+\deg_G(y)+\deg_G(z) \le (b+\Delta)+(b+\Delta)+a = n + b + 2\Delta. \tag{5} \]

Edge count. The number of edges is \[ e(G)=ab + e(H). \] If $H$ has maximum degree at most $\Delta$, then $e(H)\le a\Delta/2$. Conversely, for even $\Delta$ and $a$ large, there exists an explicit $\Delta$-regular graph on $A$ (e.g. a circulant graph connecting each vertex to its $\Delta/2$ nearest neighbours on each side on a cycle), which has exactly $a\Delta/2$ edges. So we can achieve $e(H)=\lfloor a\Delta/2\rfloor$ with maximum degree $\le\Delta$.

We choose parameters so that $e(G)>n^2/4$ while making the right-hand side of $5$ as small as possible. Write $x:=b/n$ and $y:=\Delta/n$. Then $a/n=1-x$ and (ignoring lower-order rounding errors) \[ \frac{e(G)}{n^2} \approx x(1-x) + \frac{(1-x)y}{2}. \] To have $e(G)>n^2/4$, it suffices to enforce \[ x(1-x) + \frac{(1-x)y}{2} > \frac{1}{4}. \tag{6} \] Meanwhile, $5$ gives the triangle degree-sum bound \[ \frac{1}{n}(n+b+2\Delta) = 1 + x + 2y. \tag{7} \] We now optimize $7$ subject to $6$. For fixed $x\in(0,1)$, the smallest $y$ making $6$ hold is \[ y = \frac{1}{2(1-x)} - 2x. \] Substituting into $7$ gives \[ f(x) := 1 + x + 2\left(\frac{1}{2(1-x)} - 2x\right) = 1 - 3x + \frac{1}{1-x}. \] Differentiate: \[ f'(x) = -3 + \frac{1}{(1-x)^2}. \] Setting $f'(x)=0$ gives $(1-x)^2=1/3$, i.e. $x=1-1/\sqrt{3}$. At this value, \[ f(x)=1-3\left(1-\frac{1}{\sqrt{3}}\right) + \sqrt{3} = -2 + \sqrt{3} + \frac{3}{\sqrt{3}} = 2\sqrt{3}-2 = 2(\sqrt{3}-1). \] Thus the optimal constant for this construction is exactly $2(\sqrt{3}-1)$. Choosing integers $a,b,\Delta$ with \[ \frac{b}{n}=1-\frac{1}{\sqrt{3}}+o(1),\qquad \frac{\Delta}{n}=\left(\frac{\sqrt{3}}{2}-2+\frac{2}{\sqrt{3}}\right)+o(1), \] and taking $H$ to be a (nearly) $\Delta$-regular circulant graph on $A$ yields $e(G)=n^2/4+\Omega(n)$ and $5$ gives \[ \max_{\text{triangles }T} \sum_{v\in T}\deg(v) \le \left(2(\sqrt{3}-1)+o(1)\right)n. \] This proves the lemma. $\square$

FAST REALITY CHECK (small cases / computation). By exhaustive enumeration of all labelled graphs on $n\le 7$ vertices, the exact values found are: \[ h(3)=6,\quad h(4)=8,\quad h(5)=9,\quad h(6)=10,\quad h(7)=12. \] (Here $h(n)$ is computed exactly from the definition: among graphs with $e(G)>n^2/4$, minimize the maximum degree-sum over all triangles.)

VERIFICATION.

• Lemma 1: the averaging identity $\sum_{uv\in E}(\deg u+\deg v)=\sum_v \deg(v)^2$ is checked by double-counting contributions of each vertex to its incident edges. The triangle existence step uses inclusion--exclusion and the bound $|N(u)\cup N(v)|\le n-2$.
• Lemma 2: every triangle must use two vertices from $A$ and one from $B$ because there are no edges inside $B$. Degree bounds follow from the construction. The optimization is a one-variable calculus problem. Rounding issues only contribute $o(n)$ to the degree-sum and $O(n)$ to edge counts, so the asymptotic constant is unchanged.

FINAL. UNRESOLVED.

(i) Strongest proved partial result. I proved a very weak universal lower bound $h(n)\ge n+2$ (Lemma 1) and gave a fully explicit construction showing $h(n)\le 2(\sqrt{3}-1)n+o(n)$ (Lemma 2). I also computed exact $h(n)$ for $n\le 7$.

(ii) First gap (crisp). Prove or disprove the conjectured asymptotic lower bound \[h(n)\ge (2(\sqrt{3}-1)-o(1))n.\] Equivalently: show that for every $\varepsilon>0$ and all large $n$, every graph with $e(G)>n^2/4$ has a triangle with degree-sum at least $(2(\sqrt{3}-1)-\varepsilon)n$.

(iii) Top 3 next moves. 1. Strengthen Lemma 1 by leveraging not just one large edge but correlations among high-degree vertices in graphs with $>n^2/4$ edges; target a lemma that forces a triangle whose vertices all lie in the high-degree set. 2. Attempt a stability-type argument near Mantel's theorem: if $e(G)>n^2/4$, then $G$ is close to bipartite; quantify how internal edges force triangles, and how degrees distribute between parts. 3. Extend the brute force computation to $n=8,9$ with pruning/ILP to guess the extremal structure and the correct next lower-bound constant.

(iv) What a minimal counterexample would likely look like. A graph with $e(G)=n^2/4+o(n^2)$ that is "almost" complete bipartite, with all extra edges placed inside a smaller part in a bounded-degree way, so that every triangle has two vertices in that part (bounded additional degree) and one vertex in the other part (degree about the smaller part size). Such a structure is exactly what Lemma 2 exploits.

COMPLETION ESTIMATE

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

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?\] Erdős and Laskar [ErLa85] proved\[2(\sqrt{3}-1)n \geq h(n) \geq (1+c)n\]for some $c>0$. The lower bound was improved to $\frac{21}{16}n$ by Fan [Fa88]. References [ErLa85] Erdős, Paul and Laskar, Renu, A note on the size of a chordal subgraph . Congr. Numer. $1985$, 81--86. [Fa88] Fan, Genghua, Degree sum for a triangle in a graph . J. Graph Theory $1988$, 249--263.

Erdős Problem #1033 --- Solution Attempt

FORMAL RESTATEMENT. For each integer $n\ge 3$, define $h(n)$ to be the largest integer with the property: for every simple graph $G$ on $n$ vertices with $e(G) > n^2/4$, there exists a triangle $abc$ in $G$ such that \[ \deg(a)+\deg(b)+\deg(c) \ge h(n). \] The problem asks for asymptotic estimates for $h(n)$, and in particular whether \[ h(n) \ge (2(\sqrt{3}-1)-o(1))n \] as $n\to\infty$.

QUICK LITERATURE/CONTEXT CHECK. The problem statement itself records the bounds \[ (1+c)n \le h(n) \le 2(\sqrt{3}-1)n \] for some absolute $c>0$, and that the lower bound was improved to $(21/16)n$. I do not use external results beyond what is explicitly in the problem file.

ATTACK PLAN. Proof track: derive general lower bounds on the maximum triangle degree-sum in a graph with $>n^2/4$ edges. Start from averaging arguments on degrees and edges, then force a triangle via common-neighbour counting.

Disproof/upper-bound track: construct graphs with just over $n^2/4$ edges in which every triangle has small degree-sum. A natural idea: take a complete bipartite graph $K_{a,b}$ (triangle-free, $ab$ edges) with $ab$ close to $n^2/4$, and then add a sparse graph inside the smaller part to create triangles while controlling degrees.

WORK.

Lemma 1 (Edge-sum averaging forces a "large" edge, hence a "large" triangle). Let $G$ be a graph on $n$ vertices with $m=e(G)$ edges. Then there exists an edge $uv\in E(G)$ with \[ \deg(u)+\deg(v) \ge \frac{4m}{n}. \] If moreover $m>n^2/4$, then $\deg(u)+\deg(v) > n$ and hence $u,v$ have a common neighbour $w$, so $uvw$ is a triangle with \[ \deg(u)+\deg(v)+\deg(w) \ge \frac{4m}{n} + 2. \]

Proof. For each edge $uv$, define its endpoint-degree-sum $s(uv):=\deg(u)+\deg(v)$. Sum over all edges: \[ \sum_{uv\in E(G)} s(uv) = \sum_{uv\in E(G)} (\deg(u)+\deg(v)). \] Each vertex $x$ contributes $\deg(x)$ to $s(uv)$ for each incident edge $uv$, hence contributes $\deg(x)^2$ in total. Therefore \[ \sum_{uv\in E(G)} s(uv) = \sum_{x\in V(G)} \deg(x)^2. \] By Cauchy--Schwarz, \[ \sum_{x\in V} \deg(x)^2 \ge \frac{\left(\sum_x \deg(x)\right)^2}{n} = \frac{(2m)^2}{n} = \frac{4m^2}{n}. \] Divide by $m$ to get the average value of $s(uv)$ over edges: \[ \frac{1}{m}\sum_{uv\in E} s(uv) \ge \frac{4m}{n}. \] Hence some edge $uv$ satisfies $s(uv)\ge 4m/n$.

If $m>n^2/4$, then $4m/n>n$. Now $|N(u)\cup N(v)|\le n-2$, while $|N(u)|+|N(v)|=\deg(u)+\deg(v)>n$. By inclusion--exclusion, \[ |N(u)\cap N(v)| = |N(u)|+|N(v)|-|N(u)\cup N(v)| \ge (\deg(u)+\deg(v))-(n-2) > 2, \] so in particular $N(u)\cap N(v)\neq\emptyset$. Pick $w\in N(u)\cap N(v)$; then $uvw$ is a triangle. Finally, since $w$ is adjacent to both $u$ and $v$, we have $\deg(w)\ge 2$, giving \[ \deg(u)+\deg(v)+\deg(w) \ge \frac{4m}{n} + 2. \] $\square$

Consequence. Since $m>n^2/4$ implies $4m/n\ge n+\frac{4}{n}$, Lemma 1 yields the universal bound \[ h(n) \ge n+2 \qquad (n\ge 3). \] (This is very weak compared to the conjectured constant $\approx 1.464\,n$.)

Lemma 2 (An explicit construction giving the upper bound constant $2(\sqrt{3}-1)$ up to $o(n)$). For infinitely many $n$ (and in fact for all sufficiently large $n$ after rounding), there exists a graph $G$ on $n$ vertices with $e(G)>n^2/4$ such that every triangle $T$ in $G$ satisfies \[ \sum_{v\in T} \deg(v) \le \left(2(\sqrt{3}-1)+o(1)\right)n. \] In particular, this shows \[ h(n) \le 2(\sqrt{3}-1)n + o(n). \]

Construction and proof. Fix $n$ and choose an integer $a$ close to $a\approx n/\sqrt{3}$, and let $b:=n-a$. Let $A$ and $B$ be disjoint vertex sets with $|A|=a$ and $|B|=b$. Start with the complete bipartite graph between $A$ and $B$, i.e. add all $ab$ edges between $A$ and $B$. This base graph is triangle-free. Now add a graph $H$ on the vertex set $A$ only, with maximum degree at most $\Delta$ (to be chosen), and no edges inside $B$. Let $G$ be the resulting graph.

Triangle structure. Any triangle in $G$ must use exactly two vertices from $A$ and one from $B$, because: there are no edges inside $B$, and any edge inside $A$ comes from $H$. Thus every triangle consists of an $H$-edge $xy$ in $A$ together with any vertex $z\in B$ (since all $A$--$B$ edges are present).

Degree control. Every vertex in $B$ has degree exactly $a$. Every vertex $x\in A$ has degree $\deg_G(x)=b+\deg_H(x)\le b+\Delta$. Therefore any triangle $xyz$ with $x,y\in A$ and $z\in B$ satisfies \[ \deg_G(x)+\deg_G(y)+\deg_G(z) \le (b+\Delta)+(b+\Delta)+a = n + b + 2\Delta. \tag{5} \]

Edge count. The number of edges is \[ e(G)=ab + e(H). \] If $H$ has maximum degree at most $\Delta$, then $e(H)\le a\Delta/2$. Conversely, for even $\Delta$ and $a$ large, there exists an explicit $\Delta$-regular graph on $A$ (e.g. a circulant graph connecting each vertex to its $\Delta/2$ nearest neighbours on each side on a cycle), which has exactly $a\Delta/2$ edges. So we can achieve $e(H)=\lfloor a\Delta/2\rfloor$ with maximum degree $\le\Delta$.

We choose parameters so that $e(G)>n^2/4$ while making the right-hand side of $5$ as small as possible. Write $x:=b/n$ and $y:=\Delta/n$. Then $a/n=1-x$ and (ignoring lower-order rounding errors) \[ \frac{e(G)}{n^2} \approx x(1-x) + \frac{(1-x)y}{2}. \] To have $e(G)>n^2/4$, it suffices to enforce \[ x(1-x) + \frac{(1-x)y}{2} > \frac{1}{4}. \tag{6} \] Meanwhile, $5$ gives the triangle degree-sum bound \[ \frac{1}{n}(n+b+2\Delta) = 1 + x + 2y. \tag{7} \] We now optimize $7$ subject to $6$. For fixed $x\in(0,1)$, the smallest $y$ making $6$ hold is \[ y = \frac{1}{2(1-x)} - 2x. \] Substituting into $7$ gives \[ f(x) := 1 + x + 2\left(\frac{1}{2(1-x)} - 2x\right) = 1 - 3x + \frac{1}{1-x}. \] Differentiate: \[ f'(x) = -3 + \frac{1}{(1-x)^2}. \] Setting $f'(x)=0$ gives $(1-x)^2=1/3$, i.e. $x=1-1/\sqrt{3}$. At this value, \[ f(x)=1-3\left(1-\frac{1}{\sqrt{3}}\right) + \sqrt{3} = -2 + \sqrt{3} + \frac{3}{\sqrt{3}} = 2\sqrt{3}-2 = 2(\sqrt{3}-1). \] Thus the optimal constant for this construction is exactly $2(\sqrt{3}-1)$. Choosing integers $a,b,\Delta$ with \[ \frac{b}{n}=1-\frac{1}{\sqrt{3}}+o(1),\qquad \frac{\Delta}{n}=\left(\frac{\sqrt{3}}{2}-2+\frac{2}{\sqrt{3}}\right)+o(1), \] and taking $H$ to be a (nearly) $\Delta$-regular circulant graph on $A$ yields $e(G)=n^2/4+\Omega(n)$ and $5$ gives \[ \max_{\text{triangles }T} \sum_{v\in T}\deg(v) \le \left(2(\sqrt{3}-1)+o(1)\right)n. \] This proves the lemma. $\square$

FAST REALITY CHECK (small cases / computation). By exhaustive enumeration of all labelled graphs on $n\le 7$ vertices, the exact values found are: \[ h(3)=6,\quad h(4)=8,\quad h(5)=9,\quad h(6)=10,\quad h(7)=12. \] (Here $h(n)$ is computed exactly from the definition: among graphs with $e(G)>n^2/4$, minimize the maximum degree-sum over all triangles.)

VERIFICATION.

• Lemma 1: the averaging identity $\sum_{uv\in E}(\deg u+\deg v)=\sum_v \deg(v)^2$ is checked by double-counting contributions of each vertex to its incident edges. The triangle existence step uses inclusion--exclusion and the bound $|N(u)\cup N(v)|\le n-2$.
• Lemma 2: every triangle must use two vertices from $A$ and one from $B$ because there are no edges inside $B$. Degree bounds follow from the construction. The optimization is a one-variable calculus problem. Rounding issues only contribute $o(n)$ to the degree-sum and $O(n)$ to edge counts, so the asymptotic constant is unchanged.

FINAL. UNRESOLVED.

(i) Strongest proved partial result. I proved a very weak universal lower bound $h(n)\ge n+2$ (Lemma 1) and gave a fully explicit construction showing $h(n)\le 2(\sqrt{3}-1)n+o(n)$ (Lemma 2). I also computed exact $h(n)$ for $n\le 7$.

(ii) First gap (crisp). Prove or disprove the conjectured asymptotic lower bound \[h(n)\ge (2(\sqrt{3}-1)-o(1))n.\] Equivalently: show that for every $\varepsilon>0$ and all large $n$, every graph with $e(G)>n^2/4$ has a triangle with degree-sum at least $(2(\sqrt{3}-1)-\varepsilon)n$.

(iii) Top 3 next moves. 1. Strengthen Lemma 1 by leveraging not just one large edge but correlations among high-degree vertices in graphs with $>n^2/4$ edges; target a lemma that forces a triangle whose vertices all lie in the high-degree set. 2. Attempt a stability-type argument near Mantel's theorem: if $e(G)>n^2/4$, then $G$ is close to bipartite; quantify how internal edges force triangles, and how degrees distribute between parts. 3. Extend the brute force computation to $n=8,9$ with pruning/ILP to guess the extremal structure and the correct next lower-bound constant.

(iv) What a minimal counterexample would likely look like. A graph with $e(G)=n^2/4+o(n^2)$ that is "almost" complete bipartite, with all extra edges placed inside a smaller part in a bounded-degree way, so that every triangle has two vertices in that part (bounded additional degree) and one vertex in the other part (degree about the smaller part size). Such a structure is exactly what Lemma 2 exploits.