By Mantel's theorem, every graph on n vertices with more than n²/4 edges contains a triangle. Bollobás and Erdős asked in 1975 to determine, as a function of the number of edges, the largest degree sum d(x)+d(y)+d(z) that is forced over some triangle; Erdős, Faudree, and Rousseau (1992) recalled the problem at its critical point, the Mantel threshold. Writing h(n) for the minimum, over all n-vertex graphs with ⌊n²/4⌋+1 edges, of the maximum degree sum over triangles, the best published bounds have been (21/16)n ≤ h(n) ≤ 2(√3−1)n + O(1) since 1988 (Fan's lower bound; the Erdős–Laskar construction), and the exact value, or even the leading constant, is unknown. The companion conjecture from the same 1992 paper — that such graphs have at least 2n²/9 − O(n) edges lying on cycles C2k+1C_{2k+1} — was settled in 2017–2019: refuted for C₅ by a Füredi–Maleki construction (correct constant (2+√2)/16) and proved for all k ≥ 3 by Grzesik, Hu, and Volec, who determined the exact minimum. The degree-sum problem, however, remains open: it is catalogued as open problem #1033 in the Erdős Problems database (2026), and unrefereed 2026 communications report a new blow-up construction improving the upper constant to ≈1.46388 and flag-algebra lower bounds up to ≈1.4525, so even the conjectured constant 2(√3−1) ≈ 1.4641 now appears false. The problem is to determine h(n) exactly or asymptotically.

Background

A classical theme of extremal graph theory asks what substructures are forced when a graph just exceeds a Turán-type threshold. Mantel's theorem states that a triangle-free graph on n vertices has at most ⌊n²/4⌋ edges, and Rademacher's supersaturation refinement shows that ⌊n²/4⌋+1 edges already force at least ⌊n/2⌋ triangles. A finer question is how strongly the degrees of the vertices in a forced triangle are constrained. Define, for e > n²/4, the function f(n,e) (Fan's notation; Bollobás and Nikiforov write Δ₃(n,m) for the general clique version) as the minimum, over all graphs G with n vertices and e edges, of the maximum of d(x)+d(y)+d(z) taken over all triangles xyz of G, where d(·) is the vertex degree in G. Since adding edges never decreases any degree and only adds triangles, the minimum is attained already at e = ⌊n²/4⌋+1 edges, and one writes h(n) := f(n, ⌊n²/4⌋+1). Bollobás and Erdős, in their 1975 problem list for the Fifth British Combinatorial Conference, asked to determine f(n,e) for e > n²/4. Edwards (1977) proved f(n,e) ≥ 6e/n for e ≥ n²/3, which is the r = 3 case of the Bollobás–Erdős conjecture that every n-vertex graph with m ≥ tr(n)t_r(n) edges — tr(n)t_r(n) denoting the Turán number, i.e. the maximum number of edges of a graph with no clique on r+1 vertices — contains an r-clique whose vertices have degree sum at least 2rm/n; that conjecture was proved in full by Bollobás and Nikiforov (2005), with earlier partial results by Edwards (1978) for 2 ≤ r ≤ 8 and Faudree (1992) for all r with n > (r−1)r²/4. Below the threshold n²/3, however, the function is wide open: Bollobás and Nikiforov state that for tr−1(n)<m<tr(n)t_{r-1}(n) < m < t_r(n) the value of Δr(n,m)\Delta_r(n,m) is 'essentially unknown even for r = 3', and the point m = ⌊n²/4⌋+1 (just above t₂(n) = ⌊n²/4⌋) is the first and most natural value in that unknown range. At this threshold, Erdős and Laskar (1985), in a construction arising from their study of chordal subgraphs (subgraphs with no induced cycle longer than 3 — a triangle plus all edges incident to its vertices is such a subgraph), built graphs whose every triangle has degree sum at most 2(√3−1)n + O(1) ≈ 1.4641n: a complete bipartite graph between parts of sizes k = n/√3 and l = n − k, with the remaining ⌊n²/4⌋+1 − kl edges added inside the k-side so as to create no triangles. Fan (1988) proved the matching-type lower bound f(n,e) ≥ 21e/4n, so h(n) > (21/16)n = 1.3125n; Fan also made the Erdős–Laskar construction explicit (f(n,e) < 4√(3e) − 2n + 5, which at e = ⌊n²/4⌋+1 gives 2(√3−1)n + 5 up to integer rounding) and obtained stronger bounds higher up in the range e ≥ 0.26n². These two bounds, 21/16 and 2(√3−1), have delimited the problem since 1988. The 1992 paper of Erdős, Faudree, and Rousseau — mainly about the minimum number of edges lying on odd cycles C2k+1C_{2k+1} in graphs with ⌊n²/4⌋+1 edges — recalls the degree-sum question alongside its odd-cycle problems (its bibliography cites both the Bollobás–Erdős problem list and Fan's paper).

Problem Statement

Determine h(n) := the minimum, over all graphs G on n vertices with at least ⌊n²/4⌋+1 edges (equivalently, exactly ⌊n²/4⌋+1 edges, since adding edges never decreases the maximum triangle degree sum), of the maximum of d(x)+d(y)+d(z) over all triangles xyz of G (d(v) being the degree of vertex v in G) — that is, determine the degree-sum function f(n,e) = Δ₃(n,e) of Bollobás–Erdős at the first open point e = ⌊n²/4⌋+1 of the range ⌊n²/4⌋ < e < ⌊n²/3⌋. Determine h(n) exactly (for all n, or all sufficiently large n) or asymptotically, as the leading constant c = lim h(n)/n with h(n) = cn + o(n). The published bounds are (21/16)n < h(n) ≤ 2(√3−1)n + O(1) (i.e. 1.3125n < h(n) ≲ 1.4641n), unchanged since 1988; unrefereed 2026 communications indicate 1.4525 ≲ h(n)/n ≲ 1.4639 and that the constant 2(√3−1) of the classical Erdős–Laskar construction is not optimal. It is also of interest to characterize the extremal graphs (the constructions minimizing the maximum triangle degree sum), for which no complete description is known.

References

  1. P. Erdős, R. J. Faudree, C. C. Rousseau, Extremal problems involving vertices and edges on odd cycles, Discrete Mathematics 101(1-3) (1992) 23-31, DOI 10.1016/0012-365X(92)90586-5, https://doi.org/10.1016/0012-365X(92)90586-5
  2. B. Bollobás, P. Erdős, Unsolved problems, in: Proceedings of the Fifth British Combinatorial Conference (Aberdeen, 1975), Utilitas Mathematica, Winnipeg, 1975, pp. 678-680; bibliographic record as catalogued in the Erdős Problems database, https://www.erdosproblems.com/bibs/BoEr75
  3. C. S. Edwards, The largest vertex degree sum for a triangle in a graph, Bulletin of the London Mathematical Society 9(2) (1977) 203-208, DOI 10.1112/blms/9.2.203, https://doi.org/10.1112/blms/9.2.203
  4. C. S. Edwards, Complete subgraphs with largest sum of vertex degrees, in: Combinatorics (Proc. Fifth Hungarian Colloquium, Keszthely, 1976), Colloquia Mathematica Societatis János Bolyai 18, North-Holland, Amsterdam, 1978, pp. 293-306, Zbl 0398.05049, https://zbmath.org/0398.05049
  5. P. Erdős, R. Laskar, A note on the size of a chordal subgraph, Congressus Numerantium 48 (1985) 81-86, Zbl 0647.05034, https://zbmath.org/0647.05034
  6. G. Fan, Degree sum for a triangle in a graph, Journal of Graph Theory 12(2) (1988) 249-263, DOI 10.1002/jgt.3190120216, https://doi.org/10.1002/jgt.3190120216
  7. R. J. Faudree, Complete subgraphs with large degree sums, Journal of Graph Theory 16(4) (1992) 327-334, DOI 10.1002/jgt.3190160406, https://doi.org/10.1002/jgt.3190160406
  8. B. Bollobás, V. Nikiforov, The sum of degrees in cliques, Electronic Journal of Combinatorics 12(1) (2005), article N21, DOI 10.37236/1988, arXiv:math/0410218, https://doi.org/10.37236/1988
  9. Z. Füredi, Z. Maleki, The minimum number of triangular edges and a symmetrization method for multiple graphs, Combinatorics, Probability and Computing 26(4) (2017) 525-535, DOI 10.1017/S0963548316000407, arXiv:1411.0771, https://doi.org/10.1017/S0963548316000407
  10. V. Gruslys, S. Letzter, Minimizing the number of triangular edges, Combinatorics, Probability and Computing 27(4) (2018) 580-622, DOI 10.1017/S0963548317000189, arXiv:1605.00528, https://doi.org/10.1017/S0963548317000189
  11. A. Grzesik, P. Hu, J. Volec, Minimum number of edges that occur in odd cycles, Journal of Combinatorial Theory, Series B 137 (2019) 65-103, DOI 10.1016/j.jctb.2018.12.003, arXiv:1605.09055, https://doi.org/10.1016/j.jctb.2018.12.003
  12. L. Gishboliner, B. Sudakov, Maximal chordal subgraphs, Combinatorics, Probability and Computing 32(5) (2023) 724-741, DOI 10.1017/S0963548323000068, arXiv:2205.08474, https://doi.org/10.1017/S0963548323000068
  13. T. F. Bloom (ed.), Erdős Problem #1033 (triangle degree sums in graphs with more than n²/4 edges), Erdős Problems database, last edited 3 April 2026, accessed 6 September 2026, https://www.erdosproblems.com/1033
  14. T. F. Bloom (ed.), Erdős Problem #608 (edges contained in odd cycles in graphs with more than n²/4 edges), Erdős Problems database, last edited 25 October 2025, accessed 6 September 2026, https://www.erdosproblems.com/608