Twin-free $K_r$-saturated Graphs and Maximally Independent Sets in $K_3$-free Graphs

Asier Calbet

REVIEW 3 major objections 5 minor 9 references

Twin-free $K_r$-saturated Graphs and Maximally Independent Sets in $K_3$-free Graphs

T0 review · 3 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that twin-free $K_r$-saturated graphs require asymptotically between $(r+2)n$ and $(r+3)n$ edges, and that the triangle case is bounded below by $5 + \frac{2}{3}$ times $n$ and above by $6n$.

desk verdict New twin-free saturation parameter with first bounds; the main lower bounds rely on an unproved companion theorem that a referee will need to check. read the letter →

arxiv 2411.19267 v1 pith:VMDOF6HM submitted 2024-11-28 math.CO

Asier Calbet This is my paper · ORCID

classification math.CO MSC 05C3505C6905D05

keywords twin-freesaturationK_r-saturatedgraphsK_3-freemaximalindependentsetsextremalgraphtheoryr-systemsminimumdegreeintersectingfamilies

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The classical saturation problem asks for the fewest edges in a graph that is just short of containing a clique $K_r$; the 1964 solution has many pairs of twin vertices. This paper asks what happens when twins are banned, defining $tsat(n,K_r)$ as the minimum edge count of a twin-free $K_r$-saturated graph. The main result is that $tsat(n,K_3)$ lies between $(5+\frac{2}{3})n+o(n)$ and $6n+o(n)$, while for every $r\geq 3$ the bounds $(r+2)n+o(n) \leq tsat(n,K_r) \leq (r+3)n+o(n)$ hold. A companion theorem shows twin-free $K_r$-saturated graphs exist for all sufficiently large $n$, with only four small exceptions. The proof reduces a sparse twin-free saturated graph to a tiny vertex cover plus an intersecting family of maximally independent sets in a $K_3$-free graph, which is why the triangle case carries the sharper constant.

What carries the argument

The central object is an $r$-system $(H,\mathcal{F})$: $H$ is $K_r$-free, every $S\in\mathcal{F}$ is a maximally $K_{r-1}$-free set in $H$, and any two distinct sets in $\mathcal{F}$ intersect in a set containing $K_{r-2}$. The observation that $G(H,\mathcal{F})$ is $K_r$-saturated exactly when $(H,\mathcal{F})$ is a maximal $r$-system converts saturation into extremal questions about such systems, with $s_{r,t}(m)$ bounding the size of $\mathcal{F}$ and $e_{r,t}(s)$ bounding the edges of $H$. For triangles the paper works with the variant $(3,t)'$-system that drops the intersection condition, and the two load-bearing quantitative facts are $s'_{3,3}(m)=m+O(1)$ and $e_{3,5}(s)\geq \frac{2}{3}s+o(s)$; these produce the $5+\frac{2}{3}$ triangle constant.

What would settle it

Find, for arbitrarily large $n$, a twin-free $K_3$-saturated graph on $n$ vertices with fewer than $(5+\frac{2}{3})n$ edges; equivalently, with average degree below $11\frac{1}{3}$. Such a graph would disprove the triangle lower bound of Theorem 2 outright. A less direct test would be to exhibit a $K_r$-saturated graph with $O(n)$ edges whose smallest vertex cover has size $\Omega(n)$, which would refute the companion lemma on which the proof relies.

Watch

Extended reading notes

Core claim

The central claim is that forbidding twins in $K_r$-saturated graphs raises the asymptotic edge count from the classical $(r-2)n$ to at least $(r+2)n$ and at most $(r+3)n$, with the triangle case satisfying the stronger pair of bounds $(5+\frac{2}{3})n+o(n)$ and $6n+o(n)$. The same linear bounds hold for the minimum-degree refinement $tsat(n,K_r,t)$ whenever $t\leq r+2$ (for triangles, $t\leq 5$), while for larger $t$ the excess over $tn$ is a sublinear power of $n$: the range is $\Omega(n^{1/(t-r+2)})$ to $O(n^{4/(t-r+2)})$, with improved triangle exponents. The lower-bound method passes through a vertex cover of size $O(n/\log n)$: outside the cover, every vertex is represented by its neighbourhood, and the saturated condition turns these neighbourhoods into a family of maximally $K_{r-1}$-free sets with pairwise intersections containing a $K_{r-2}$, a structure the paper calls an $r$-system. Estimating the extremal functions of these systems yields the linear constants; explicit constructions of $K_3$-free graphs with many size-$t$ maximally independent sets supply the matching upper bounds.

Load-bearing premise

The lower-bound proofs depend on a structural lemma proved in the companion paper, not here: every $K_r$-saturated graph with linearly many edges has a vertex cover of size $O(n/\log n)$, and if that lemma fails the counting argument behind the $(r+2)n$ and $(5+\frac{2}{3})n$ lower bounds collapses.

Editorial extensions

If this is right

If the lower bounds are right, the twin-free condition changes the asymptotic constant for clique saturation from $(r-2)n$ to somewhere between $(r+2)n$ and $(r+3)n$, more than doubling it for triangles.
The triangle constant is tied to size-five maximally independent sets in $K_3$-free graphs: any improvement on $e_{3,5}(s)\geq \frac{2}{3}s+o(s)$ would directly improve the $5+\frac{2}{3}$ lower bound.
For the minimum-degree variant $tsat(n,K_r,t)$, the same linear asymptotics hold for all small $t$, so a low minimum-degree requirement does not force extra edges beyond the twin-free baseline; for larger $t$ the excess over $tn$ grows as a sublinear power of $n$.
Twin-free $K_r$-saturated graphs exist for every $n$ except $n=r$, $n=r+1$, and the two small triangle cases $n=6,7$, so the problem is well-posed for all large orders.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Editorial extension: the small-vertex-cover reduction may be a general route to proving $tsat(n,H)=\Omega(n)$ for other forbidden graphs $H$ whose extremal saturators are blow-ups, turning twin-free saturation into an intersecting-family problem for general $H$.
Editorial extension: the gap between $5\frac{2}{3}n$ and $6n$ for triangles is concrete; a computational search on twin-free $K_3$-saturated graphs with, say, $n$ up to a few hundred could indicate whether the true constant sits closer to the lower obstruction or to the $6n$ construction.
Editorial extension: if the companion vertex-cover lemma could be upgraded from $O(n/\log n)$ to $o(n)$ with explicit constants, the method would yield a fully self-contained proof of the linear lower bounds without relying on an external paper's structural theorem.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The paper defines tsat(n,K_r), the minimum number of edges in a twin-free K_r-saturated graph, and gives the first bounds: (r+2)n ≤ tsat(n,K_r) ≤ (r+3)n, with a stronger lower bound (5+2/3)n for r=3. That is a genuinely new parameter and a clean pair of theorems. The existence classification in Theorem 1 is complete and also new. The r-systems framework is a reasonable abstraction, and the auxiliary results — s_{r,t}(m), e_{r,t}(s), the exact s'_{3,3}(m)=m+O(1), and the constant 2/3 lower bound on e_{3,5}(s) — are substantial. The connection to maximizing and minimizing maximally independent sets in K3-free graphs is a useful byproduct and likely to be cited independently.

The main soft spot is the lower-bound machinery. Both Theorem 2 and Theorem 3 lower bounds assume Theorem 4 of the companion paper [1]: every K_r-saturated graph with O(n) edges has a vertex cover of size O(n/log n). That theorem is not stated or proved here, and it is doing real work: without the o(n) size, the counting of small-degree vertices outside the cover gives only (r+1)n. The companion paper is listed as to appear in the Electronic Journal of Combinatorics, so this may be a legitimate dependency, but a referee cannot check the heart of the paper without that external result. The paper would be stronger if it stated the theorem precisely or proved a sufficiently strong special case. I would want the referee to verify [1] carefully.

There are also a lot of 'it is easy to check' steps, especially in Theorem 1's small-case classification and the constructions. Most are probably fine, but in a proof where the main structural facts come from an external paper, this style adds friction. Section 4 is long; the proof of Theorem 9 is intricate and self-contained — credit where it is due.

All that said, the central argument is not circular; the auxiliary quantities are defined independently, and the bounds are not fitted. If [1, Thm 4] holds, the paper's main results follow as stated. I do not see a load-bearing flaw in the internal reasoning on a first read, just an external dependency that needs checking.

The paper is for people working on saturation numbers, and possibly on maximal independent set counts in sparse graphs. It deserves a serious referee, but the reviewer should read [1] first, or at minimum demand a precise statement of its Theorem 4. My recommendation: send it to peer review, with a referee brief that flags the companion theorem. I would cite it in my own work on saturation.

Referee Report

3 major / 5 minor

Summary. The paper studies twin-free K_r-saturated graphs. It introduces tsat(n,K_r) and the minimum-degree variant tsat(n,K_r,t), proves a complete existence characterization in Theorem 1, and gives two-sided linear bounds in Theorems 2 and 3. The central quantitative claims are (5+2/3)n+o(n) ≤ tsat(n,K3) ≤ 6n+o(n), (r+2)n+o(n) ≤ tsat(n,K_r) ≤ (r+3)n+o(n) for r ≥ 4, and analogous bounds with sublinear corrections for tsat(n,K_r,t) when t ≥ r+3. The proofs are organized around r-systems and auxiliary extremal quantities s_{r,t}(m), e_{r,t}(s), and e'_{r,t}(s), with estimates developed in Theorems 4 through 8.

Significance. If the main theorems are correct, this is a meaningful contribution to saturation theory: it isolates the effect of twin-freeness on the classical Erdős–Hajnal–Moon extremal construction, gives an exact existence characterization, and establishes two-sided bounds with explicit constants. The r-system framework and the associated extremal problems for maximally independent sets of fixed size in triangle-free graphs are natural and likely to be reused. The paper contains explicit constructions and a long chain of estimates, and I did not find evidence of parameter fitting or circular reasoning: the auxiliary quantities are defined independently of the claimed bounds. The main reservation is that the lower-bound proofs depend on structural results from the companion paper [1] that are neither stated nor proved in the present manuscript, which makes the central claims conditional as written.

major comments (3)

[Section 4, proof of Theorem 2 lower bounds] The lower-bound halves of Theorem 2 (and the analogous lower bounds in Theorem 3) invoke [1, Theorem 4] to obtain a vertex cover C of size m = O(n/log n). This theorem is load-bearing: the subsequent estimates |F_t| ≤ s_{r,t}(m) = O(m) only imply that the number of vertices outside C of degree at most r+1 is O(m), and the claimed coefficient r+2 (or 17/3 for r=3) requires m = o(n). If [1, Theorem 4] is false, has hidden hypotheses, or applies only to a restricted class of K_r-saturated graphs, the lower bound reduces to (r+1)n. Since the theorem is not stated or proved in this paper and is not a standard textbook result, the revision should state it precisely, verify that the present hypotheses match it, and either prove it or give a self-contained substitute.
[Section 4, proof of Theorem 8] The proof of Theorem 8 begins with 'By Lemma 4 in [1]' and then uses the set S and the alternative inequalities involving |Γ(v)∩S| and |Γ(v)\S|. Parts 1 and 2 of Theorem 3 are derived from Theorem 8, so this is a second external load-bearing lemma. The manuscript does not state Lemma 4 or its hypotheses, so the proof of Theorem 8 cannot be checked from the text as it stands. The revision should include the statement and proof, or at minimum show explicitly that the hypotheses of the present paper (δ(G) ≥ t and the twin-pair condition) satisfy the lemma.
[Section 4, proof of Theorem 3 lower bounds] With H = G[C ∪ S], the displayed identity e(G) = e(H) + e(C, V(G)\C) is not correct: it counts the edges between C and S twice. The correct decomposition is e(G) = e(H) + e(C, V(G)\(C∪S)), equivalently e(G) = e(C) + e(C, V(G)\C). Because |S| ≤ t|C| = O(n/log n), the resulting asymptotic lower bound is unchanged up to an O(n/log n) error, but the displayed equality should be repaired or replaced by an inequality with this error term.

minor comments (5)

[Proof of Theorem 1] The sentence 'Adding r−3 conical vertices then gives a twin-free Kr-saturated graph on r+k vertices' should read 'on k+r−3 vertices'; as written the vertex count is inconsistent with the preceding construction.
[Section 4, proof of Theorem 2 lower bounds] The estimate e(G) ≥ (r+2)n + O(n/log n) should be written as e(G) ≥ (r+2)n − O(n/log n); with plus O the displayed inequality is misleading because the O(n/log n) vertices outside C of degree at most r+1 subtract from the ideal count.
[Statements of Theorems 3, 6, and 8] The notation e'_{r,t}[n+o(n)] uses a real-valued argument; please clarify that it means for every integer N = n+o(n) (or for the least such integer) and that the estimates are uniform.
[Construction 1] Property 5 in Construction 1, including the maximality of (H'_{t,l},F'_{t,l}) and the O(l^3) bound on missing edges for t=4, is asserted as 'easy to check' and is used in the upper bounds of Theorems 2 and 6; a proof or a detailed verification would strengthen the paper.
[Throughout] There are several small typos: 'turn out be' in the abstract, 'is is roughly' in Section 3, and 'Theoerem' in Remark 3.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation: the bounds follow from independently defined r-system quantities; the only self-citation is the companion vertex-cover theorem, which is a verification dependency rather than a circular step.

full rationale

The paper defines tsat(n,K_r) and tsat(n,K_r,t) in terms of twin-free, minimal K_r-saturated graphs, and separately defines r-systems (H,F), s_{r,t}(m), and e_{r,t}(s). None of these definitions contains the target estimate (r+2)n or (5+2/3)n; the bounds are obtained by explicit constructions and counting arguments rather than by renaming an input. The upper bounds are self-contained through Lemmas 2-3, Construction 1, and Theorems 4-6. The lower bounds in Theorems 2 and 3 invoke the author's prior Theorem 4 from [1] to find a vertex cover C of size m=O(n/log n) in any O(n)-edge K_r-saturated graph. This is the only load-bearing self-citation. It is not circular: [1] is a separate structural theorem about K_r-saturated graphs with linear edge count and does not presuppose the twin-free tsat bounds or the r-system estimates proved here. If that theorem were false or misstated, the O(n/log n) count would become an O(n) error and the lower bounds would degrade; that is a correctness or verification risk, not an equivalence-by-construction. No fitted parameter is renamed as a prediction, no uniqueness theorem is imported to force a choice, and no known result is repackaged as new. Overall the derivation chain is non-circular, with only a modest self-citation dependency.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters are fitted to data; this is a pure mathematics paper. The central results rest on several external theorems, the most important being Theorem 4 of the author's companion paper [1], which is not proved here. The r-systems and related quantities are new definitions rather than postulated entities.

assumptions (4)

domain assumption Theorem 4 of [1]: every K_r-saturated graph with e(G)=O(n) has a vertex cover of size O(n/log n).
Used in the lower bound proofs of Theorems 2 and 3 (Section 4, 'by Theorem 4 in [1]...'). Not proved here; from the author's companion paper.
standard math Erdős-Ko-Rado intersection theorem
Used in Theorem 4 part 5 upper bound to bound |F| by an intersection condition on families of t-sets.
standard math Hajnal's theorem: every K_r-saturated graph with minimum degree below 2(r-2) has a conical vertex
Used in Section 3 to derive evidence for Conjectures 2-5 and to prove structural facts about (r,t)-systems.
standard math Erdős-Hajnal-Moon theorem: sat(n,K_r) = (r-2)n - binom(r-1,2)
Baseline for the trivial lower bound and for the definition of sat(n,K_r) in the introduction.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Twin-free $K_r$-saturated Graphs and Maximally Independent Sets in $K_3$-free Graphs." pith.science (2026). https://pith.science/paper/VMDOF6HM

@misc{pith2026241119267,
  author       = {Pith},
  title        = {Pith review of: Twin-free $K_r$-saturated Graphs and Maximally Independent Sets in $K_3$-free Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VMDOF6HM}},
  note         = {Machine review of arXiv:2411.19267}
}

abstract

We say that two vertices are twins if they have the same neighbourhood and that a graph is $K_r$-saturated if it does not contain $K_r$ but adding any new edge to it creates a $K_r$. In 1964, Erd\H{o}s, Hajnal and Moon showed that $sat(n,K_r)=(r-2)n+o(n)$ for $r \geq 3$, where $sat(n,K_r)$ is the minimum number of edges in a $K_r$-saturated graph on $n$ vertices, and determined the unique extremal graph. This graph has many twins, leading us to define $tsat(n,K_r)$ to be the minimum number of edges in a twin-free $K_r$-saturated graph on $n$ vertices. We show that $(5 +2/3)n + o(n) \leq tsat(n,K_3) \leq 6n+o(n)$ and that $\left(r+2\right)n + o(n) \leq tsat(n,K_r) \leq (r+3)n+o(n)$ for $r \geq 4$. We also consider a variant of this problem where we additionally require the graphs to have large minimum degree. Both of these problems turn out be intimately related to two other problems regarding maximally independent sets of a given size in $K_3$-free graphs and generalisations of these problems to $K_r$ with $r \geq 4$. The first problem is to maximise the number of maximally independent sets given the number of vertices and the second problem is to minimise the number of edges given the number of maximally independent sets. They are interesting in their own right.

Figures

Figures reproduced from arXiv: 2411.19267 by the authors.

**Figure 1.** The set S and the sets Sv. We show that every vertex v ∈ S is adjacent to all vertices except for those in S ∪ Sv and that there are no other edges in H and sets in F. Hence s = 4. Let S = {a, b, c}. By condition 2 in Definition 6, every vertex in the induced subgraph between {b, c} and Sa\{a} has degree at least one. It is easy to check that every bipartite graph with two vertices in each part in which every vertex… view at source ↗

**Figure 2.** The sets Sv. By condition 2 in Definition 6, v is adjacent to v ′ for all v ∈ S. Let x ∈ V (H) \ U, where U = S ∪ S ′ and 14 [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗

**Figure 3.** The sets S and T . Let S = {a, b, c} and T = {a, b, d}. Then by condition 2 in Definition 6, c is adjacent to d. Hence, for every vertex v ∈ V (H) \ {a, b, c, d}, by condition 1 in Definition 6, v cannot be adjacent to both c and d, so by condition 2 in Definition 6, v must be adjacent to a or b. For every such vertex v, pick a vertex in {a, b} that v is adjacent to and let X and Y be the sets of vertices v for whic… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

9 extracted references · 3 canonical work pages

[1]

A. Calbet. Kr-saturated Graphs and the Two Families Theorem. To appear in the Electronic Journal of Combinatorics. Preprint: arXiv:2302.13389

work page Pith review arXiv
[2]

B. L. Currie, J. R. Faudree, R. J. Faudree and J. R. Schmitt. A Survey of Minimum Saturated Graphs. The Electronic Journal of Combinatorics, DS19: Oct 11, 2021. doi: 10.37236/41

doi:10.37236/41 2021
[3]

D. A. Duﬀus and D. Hanson. Minimal k-saturated and color critical graphs of prescribe d minimum degree . Journal of Graph Theory, 10(1), pp. 55-67, 1986. doi: 10.1002/ jgt.3190100109

work page 1986
[4]

Erd˝ os, A

P. Erd˝ os, A. Hajnal and J. W. Moon. A problem in graph theory . American Mathematical Monthly, 71(10), pp. 1107–1110, 1964. doi:10.2307/2311408

doi:10.2307/2311408 1964
[5]

Erd˝ os, C

P. Erd˝ os, C. Ko and R. Rado. Intersection theorems for systems of ﬁnite sets . Quarterly Journal of Math- ematics, 2(12), pp. 313-320, 1961. doi:10.1093/qmath/12.1.313

doi:10.1093/qmath/12.1.313 1961
[6]

A. Hajnal. A theorem on k-saturated graphs . Canadian Journal of Mathematics, 17, pp. 720–724, 1965. doi:10.4153/CJM-1965-072-1

doi:10.4153/cjm-1965-072-1 1965
[7]

K´ aszonyi and Z

L. K´ aszonyi and Z. Tuza. Saturated graphs with minimal number of edges. Journal of Graph Theory, 10(2), pp. 203-210, 1986. doi:10.1002/jgt.3190100209

doi:10.1002/jgt.3190100209 1986
[8]

Song and B

C. Song and B. Yao. Maximizing the number of maximal independent sets of a ﬁxed s ize. arXiv preprint: arXiv:2012.06066

arXiv 2012

Show all 9 references

[9]

Z. Tuza. A generalization of saturated graphs for ﬁnite languages. Tanulm´ anyok-MTA Sz´ amit´ astech. Au- tomat. Kutat´ o Int. Budapest, (185), pp. 287-293, 1986. 25

1986

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [1]

A. Calbet. Kr-saturated Graphs and the Two Families Theorem. To appear in the Electronic Journal of Combinatorics. Preprint: arXiv:2302.13389

work page Pith review arXiv

[2] [2]

B. L. Currie, J. R. Faudree, R. J. Faudree and J. R. Schmitt. A Survey of Minimum Saturated Graphs. The Electronic Journal of Combinatorics, DS19: Oct 11, 2021. doi: 10.37236/41

doi:10.37236/41 2021

[3] [3]

D. A. Duﬀus and D. Hanson. Minimal k-saturated and color critical graphs of prescribe d minimum degree . Journal of Graph Theory, 10(1), pp. 55-67, 1986. doi: 10.1002/ jgt.3190100109

work page 1986

[4] [4]

Erd˝ os, A

P. Erd˝ os, A. Hajnal and J. W. Moon. A problem in graph theory . American Mathematical Monthly, 71(10), pp. 1107–1110, 1964. doi:10.2307/2311408

doi:10.2307/2311408 1964

[5] [5]

Erd˝ os, C

P. Erd˝ os, C. Ko and R. Rado. Intersection theorems for systems of ﬁnite sets . Quarterly Journal of Math- ematics, 2(12), pp. 313-320, 1961. doi:10.1093/qmath/12.1.313

doi:10.1093/qmath/12.1.313 1961

[6] [6]

A. Hajnal. A theorem on k-saturated graphs . Canadian Journal of Mathematics, 17, pp. 720–724, 1965. doi:10.4153/CJM-1965-072-1

doi:10.4153/cjm-1965-072-1 1965

[7] [7]

K´ aszonyi and Z

L. K´ aszonyi and Z. Tuza. Saturated graphs with minimal number of edges. Journal of Graph Theory, 10(2), pp. 203-210, 1986. doi:10.1002/jgt.3190100209

doi:10.1002/jgt.3190100209 1986

[8] [8]

Song and B

C. Song and B. Yao. Maximizing the number of maximal independent sets of a ﬁxed s ize. arXiv preprint: arXiv:2012.06066

arXiv 2012