Let C_[4,r]=C_4,C_5,…,C_r. For every integer r≥ 5, there exists an integer n_0(r) such that, for every n≥ n_0(r), operatornamesat(n,C_[4,r])=lceil frac5n4-frac32rceil, where operatornamesat(n,C_[4,r]) is the minimum number of edges in an n-vertex graph containing no cycle C_i for 4≤ i≤ r, but such that adding any missing edge creates a copy of at least one such cycle.

Ma’s saturation-number conjecture

Let $\mathcal{C}_{[4,r]}=\{C_4,C_5,\ldots,C_r\}$ . For every integer $r\ge 5$ , there exists an integer $n_0(r)$ such that, for every $n\ge n_0(r)$ , $\operatorname{sat}(n,\mathcal{C}_{[4,r]})=\left\lceil\frac{5n}{4}-\frac{3}{2}\right\rceil$ , where $\operatorname{sat}(n,\mathcal{C}_{[4,r]})$ is the minimum number of edges in an $n$ -vertex graph containing no cycle $C_i$ for $4\le i\le r$ , but such that adding any missing edge creates a copy of at least one such cycle.

Progress summary

Partially solved

A new paper disproves the conjecture once the forbidden cycle range includes length six, proves the length-six case exactly, and leaves longer ranges unresolved.

Ma’s conjecture predicts that, for every $r \ge 5$ , the saturation number for the interval of cycles from $C_4$ through $C_r$ eventually equals $\left\lceil \frac{5n}{4}-\frac{3}{2}\right\rceil$ .

Known results

The exact formula $\operatorname{sat}(n,\mathcal{C}_{\{4,5\}})=\left\lceil \frac{5n}{4}-\frac{3}{2}\right\rceil$ was known for every positive integer $n$ .

19 August 2026 disproof for $r \ge 6$

The new paper proves a stronger upper bound with an $r$ -dependent subtraction, establishes $\operatorname{sat}(n,\mathcal{C}_{[4,6]})$ exactly, and thereby disproves the conjectured eventual formula for every $r \ge 6$ . It does not determine the exact saturation number for every $r \ge 7$ .

Current status (as of August 2026): The conjecture is false for every $r \ge 6$ , and the case $r=6$ is settled exactly; the exact values for all $r \ge 7$ remain open.

Sources

arxiv.org

Sources & referencesView supporting material

Primary source

arXiv

Additional references

Minimizing the number of edges in C_[4,6]-saturated graphs — arXiv

extremal-graph-theory

1 day ago