The regime $c<2/5$ of the edge-minimum function $K(c)$ for maximal triangle-free graphs with bounded maximum degree

The minimum number of edges in a maximal triangle-free graph on $n$ vertices with maximum degree at most $D$ is denoted $F(n,D)$. Füredi and Seress (1994) proved that the limit $K(c)=\lim_{n\to\infty}F(n,cn)/n$ exists for every $0<c\leq 1$ outside a possible exceptional sequence tending to $0$, determined $F(n,D)$ exactly for $D\geq(n-2)/2$, and conjectured $K(c)=q+2$ on $[(q+1)/(q^2+q+1),\,1/q)$ whenever the projective plane $PG(2,q)$ exists. Erdős and Holzman (1994) determined $K(c)=4$ on $[2/5,3/7]$ and $K(c)=(11-7c)/2$ on $[3/7,1/2)$, refuting the conjecture's first instance ($q=2$), and left open the behaviour to the left of $2/5$: a Fano-plane-based construction gives $K(c)\leq 7-7c$ on $[1/3,2/5)$ and is suggested to be optimal there; the optimality ranges of the $PG(2,q)$-generalized constructions are unknown; the conjecture for $q\geq 3$ and the boundary values $K((q+1)/(q^2+q+1))$ are unsettled; and it is unknown whether $K$ has infinitely many discontinuities. No published work determines $K(c)$ on any subinterval of $(0,2/5)$; the problem remains open.

Background

A graph is triangle-free if it contains no three pairwise adjacent vertices, and maximal triangle-free if, in addition, every missing edge, when inserted, completes a triangle; equivalently, a maximal triangle-free graph is a $K_3$-saturated graph (saturated with respect to the complete graph $K_3$ on three vertices, i.e. $K_3$-free but such that every added edge creates a $K_3$) or, since any two non-adjacent vertices must then share a common neighbour, a triangle-free graph of diameter 2. The classical saturation theorem of Erdős, Hajnal and Moon (1964) states that an $n$-vertex $K_3$-saturated graph has at least $n-1$ edges; the unique extremal example, a star, has a vertex of degree $n-1$, so the unconstrained minimum is attained only by graphs with very large degrees. This motivates the degree-restrained variant of Füredi and Seress (1994): let $F(n,D)$ be the minimum number of edges of a maximal triangle-free graph on $n$ vertices with maximum degree at most $D$. A counting argument shows $D$ must be at least on the order of $n^{1/2}$ (a vertex together with the neighbours of its neighbours must cover all $n$ vertices), and the elementary bound $m\geq n(n-1)/(2D)$ (each vertex has degree at least $(n-1)/D$) gives $F(n,cn)\geq(1/(2c)-o(1))n$; but the true answer in the linear regime $D=cn$, $0<c\leq 1$, is larger and structurally subtle. Füredi and Seress proved that the limit $K(c)=\lim_{n\to\infty}F(n,cn)/n$ exists for every $0<c\leq 1$ with the possible exception of a sequence of values tending to $0$, determined $F(n,D)$ exactly for $D\geq(n-2)/2$ (that is, $K$ on $[1/2,1]$), and gave only constant-factor bounds for the sublinear regime $D=cn^{\epsilon}$, $1/2<\epsilon<1$. Their central tool, sharpened by Erdős and Holzman, is a reduction to finite linear programming: a core is a pair $(H,G)$ where $H$ is an intersecting hypergraph (any two hyperedges intersect) and $G$ a triangle-free graph on the same finite vertex set, satisfying compatibility axioms; to $H$ is attached the linear program minimizing $\sum_i|H_i|y_i$ subject to $\sum_{H_i\ni x}y_i\leq c$ for every vertex $x$, $y_i\geq 0$, $\sum_i y_i=1$, feasible precisely when $c\geq 1/\nu^*(H)$, where $\nu^*(H)$ is the fractional matching number of $H$ (the maximum total weight on hyperedges subject to each vertex being covered by weight at most $1$). Blowing up hyperedges into vertex classes yields maximal triangle-free graphs with about $A(H,c)\cdot n$ edges for the LP optimum $A(H,c)$, and $K(c)$ is the infimum of $A(H,c)$ over cores; on every interval $[\gamma,\infty)$ this becomes a finite problem. Constructions from finite geometry drive the conjectured values: the projective plane $PG(2,q)$ (which exists for every prime power $q$; existence for other orders is a long-standing open problem) has $q^2+q+1$ points and lines of $q+1$ points, its lines forming an intersecting hypergraph with $\nu^*=(q^2+q+1)/(q+1)$, and $(q+1)/(q^2+q+1)$ is the fraction of points on a line — the endpoints of the conjectured intervals. Erdős and Holzman (1994) determined the middle window: $K(c)=4$ for $2/5\leq c\leq 3/7$ (attained by a core built from the Petersen graph, the 3-regular graph on 10 vertices, whose five independent 4-sets carry the uniform weight $1/5$) and $K(c)=(11-7c)/2$ for $3/7\leq c<1/2$. Since $(11-7c)/2<4$ strictly to the right of $3/7$, this refuted the first instance ($q=2$) of the Füredi–Seress conjecture that $K(c)=q+2$ on $[(q+1)/(q^2+q+1),\,1/q)$ whenever $PG(2,q)$ exists. The easier-looking variant without triangle-freeness — graphs of diameter 2, i.e. $K_3$-semisaturated graphs, where added edges must create a triangle but pre-existing triangles are allowed — has a parallel limit function, determined for $c\geq 3/7$ with a leading-term conjecture of Füredi on $(1/3,3/7)$; the two problems are distinct, and the triangle-free (saturation) problem treated here is the one left with an undetermined window below $2/5$.

Problem Statement

Determine $K(c)=\lim_{n\to\infty}F(n,cn)/n$ for maximal triangle-free graphs — where $F(n,D)$ is the minimum number of edges of a maximal triangle-free graph on $n$ vertices with maximum degree at most $D$ — throughout the remaining window $0<c<2/5$, at every point where the limit exists. That is, extend the determination of Erdős and Holzman, which covers $[2/5,1/2)$, and of Füredi and Seress, which covers $[1/2,1]$, to the left of $2/5$. The paper of Erdős and Holzman poses this window through the following explicit facets: (i) the suggested value $K(c)=7-7c$ for $1/3\leq c<2/5$, where the Fano-plane-based construction (the Fano plane being the projective plane $PG(2,2)$) gives $K(c)\leq 7-7c$ — prove this optimal or find the correct value; (ii) the optimality ranges of the generalizations of that construction obtained by replacing the Fano plane by $PG(2,q)$; (iii) the Füredi–Seress conjecture for $q\geq 3$, that $K(c)=q+2$ on $[(q+1)/(q^2+q+1),\,1/q)$ when $PG(2,q)$ exists — the first instance $q=2$ is refuted, and it is open whether the failure is exceptional or systematic — together with the boundary values $K((q+1)/(q^2+q+1))$ for $q\geq 3$; and (iv) whether $K$ has infinitely many discontinuities (the limit is known to exist everywhere except possibly on a sequence tending to $0$, and the source paper notes that this determination creates a discontinuity at $c=1/2$, where the left limit of $K$ is $15/4$). These four facets are independently meaningful sub-questions: settling any one of them resolves that part of the problem, whereas the overall objective remains the determination of $K(c)$ throughout $(0,2/5)$, which the facets do not by themselves exhaust.

References

1. Paul Erdős and Ron Holzman, On maximal triangle-free graphs, Journal of Graph Theory 18(6):585–594, 1994. DOI: 10.1002/jgt.3190180606, https://doi.org/10.1002/jgt.3190180606
2. Zoltán Füredi and Ákos Seress, Maximal triangle-free graphs with restrictions on the degrees, Journal of Graph Theory 18(1):11–24, 1994. DOI: 10.1002/jgt.3190180103, https://doi.org/10.1002/jgt.3190180103
3. Zoltán Füredi, Intersecting designs from linear programming and graphs of diameter two, Discrete Mathematics 127(1–3):187–207, 1994. DOI: 10.1016/0012-365X(92)00478-A, https://doi.org/10.1016/0012-365X(92)00478-A
4. Noga Alon, Paul Erdős, Ron Holzman and Michael Krivelevich, On k-saturated graphs with restrictions on the degrees, Journal of Graph Theory 23(1):1–20, 1996. DOI: 10.1002/(SICI)1097-0118(199609)23:1<1::AID-JGT1>3.0.CO;2-O, https://doi.org/10.1002/(SICI)1097-0118(199609)23:1%3C1::AID-JGT1%3E3.0.CO;2-O
5. Zhen He, Mei Lu, Yanzhe Qiu and Yiduo Xu, Degree-restricted semi-saturation numbers of cliques and its applications, preprint, 2026. arXiv:2606.28727, https://arxiv.org/abs/2606.28727
6. P. Erdős, A. Hajnal and J. W. Moon, A Problem in Graph Theory, The American Mathematical Monthly 71:1107–1110, 1964. DOI: 10.2307/2311408, https://doi.org/10.2307/2311408
7. Curtiss Barefoot, Karen Casey, David Fisher, Kathryn Fraughnaugh and Frank Harary, Size in maximal triangle-free graphs and minimal graphs of diameter 2, Discrete Mathematics 138(1–3):93–99, 1995. DOI: 10.1016/0012-365X(94)00190-T, https://doi.org/10.1016/0012-365X(94)00190-T
8. Wayne Goddard and Daniel J. Kleitman, A note on maximal triangle-free graphs, Journal of Graph Theory 17(5):629–631, 1993. DOI: 10.1002/jgt.3190170510, https://doi.org/10.1002/jgt.3190170510
9. A. Nicholas Day, Saturated Graphs of Prescribed Minimum Degree, Combinatorics, Probability and Computing 26(2):201–207, 2017. DOI: 10.1017/S0963548316000377, https://doi.org/10.1017/S0963548316000377
10. Bryan L. Currie, Jill R. Faudree, Ralph J. Faudree and John R. Schmitt, A Survey of Minimum Saturated Graphs, Electronic Journal of Combinatorics, Dynamic Survey DS19, 2011 (with later updates). DOI: 10.37236/41, https://doi.org/10.37236/41