Pith. sign in

REVIEW 2 major objections 4 minor 2 cited by

Minimum degree and sparse connected spanning subgraphs

T0 review · 2 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read For $n\ge 6k^3$, an $n$-vertex graph with minimum degree at least $n-k$ contains every sparse connected $n$-vertex graph whose $\alpha'$ parameter is at least $k-1$.

desk verdict Solid generalization of the tree-star Ramsey theorem with a real gap in the t-star extension; Theorem 4 deserves referee time, Theorem 5 needs a fix. read the letter →

arxiv 2507.03264 v1 pith:BHGHBU3Q submitted 2025-07-04 math.CO

Ting Huang , Yanbo Zhang , Yaojun Chen This is my paper · ORCID
classification math.CO MSC 05C5505C3505C70
keywords Ramseynumberspanningsubgraphminimumdegreestargraphsparsetreetrichotomysuspendedpathmatching
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

This paper proves that the classical tree theorem of [5] extends from trees to all sparse connected graphs. The main result is a two-sided bound on the Ramsey number $r(G,K_{1,k})$: for $n\ge 6k^3$ and a connected $G$ on $n$ vertices with at most $n(1+1/(24k-12))$ edges, the value lies between $\max\{n,n+k-1-\alpha'-\beta\}$ and $\max\{n,n+k-1-\alpha'\}$, where $\alpha'=\min_v\alpha(G-N[v])$ and $\beta$ is a parity correction. The spanning-subgraph consequence is that every $n$-vertex graph $F$ with minimum degree at least $n-k$ contains every such $G$ with $\alpha'\ge k-1$ as a spanning subgraph. A parallel bound is proved for $r(G,tK_{1,k})$, the Ramsey number against $t$ disjoint stars.

What carries the argument

The argument is carried by an enhanced tree trichotomy for sparse graphs, stated as Lemma 1 in [8]. It says that a connected graph on $n$ vertices with $n+\ell$ edges either has a suspended path of length $q$ (a path whose internal vertices have degree 2), or a matching of $s$ end-edges, or a vertex adjacent to roughly $n/(s-1)$ leaves. Around this, the proof builds a reduction engine: Lemma 8 shows $r(G,K_{1,k})\le n+2k-2$ for any connected graph with at most $n(1+1/(2k+1))$ edges, by repeatedly deleting or suppressing vertices of degree at most 2 and then extending the embedded smaller graph back using red neighborhoods. In the three cases the proof shortens a suspended path and re-extends it, completes a matching of end-edges via Hall's theorem, or embeds a leaf-heavy graph and uses the large red neighborhood of one vertex; the parameter $\alpha'(G)$ controls how many vertices of an independent set in $G-N[u]$ must be accounted for when avoiding a blue star.

What would settle it

To test the central reduction, compute $\alpha'$ for the graph $H$ obtained from a sparse connected $G$ by shortening one suspended path by $2k-2$ vertices; if $\alpha'(H)<\alpha'(G)$, substitute $\alpha'(H)$ into the claimed bound and check whether $r(H,K_{1,k})\le n$ still follows, since the proof of Case 1 needs exactly that inheritance.

Watch

Extended reading notes

Core claim

Stated on the paper's own terms, the discovery is a tight Ramsey evaluation. For $k\ge 1$, $n\ge 6k^3$, and a connected graph $G$ on $n$ vertices with $e(G)\le n(1+1/(24k-12))$ and $\alpha'(G)=\alpha'$, the paper establishes $\max\{n,n+k-1-\alpha'-\beta\}\le r(G,K_{1,k})\le \max\{n,n+k-1-\alpha'\}$, with $\beta=0$ if $k\mid n+k-2-\alpha'$ and $\beta=1$ otherwise. This reproduces, for general sparse connected graphs, the bounds that [5] proved for trees, and it lowers the required size of $n$ from $O(k^3)$ to $6k^3$. When $\alpha'\ge k-1$ the bounds collapse to $r(G,K_{1,k})=n$, which is exactly the statement that $\delta(F)\ge n-k$ forces $G$ as a spanning subgraph of $F$. For $t$ copies of the star the paper proves $r(G,tK_{1,k})\le \max\{n,n+k-1-\alpha'\}+t-1$ for $n\ge 28t^2k^3$, with equality $n+t-1$ in the case $\alpha'\ge k-1$.

Load-bearing premise

The reductions that produce a smaller graph $H$ from $G$, by deleting end-vertices or shortening a suspended path, are applied while keeping the original value $\alpha'(G)$ in the Ramsey bound for $H$; if $\alpha'(H)$ can be smaller than $\alpha'(G)$, those bounds may not hold.

Editorial extensions

If this is right

  • For $n\ge 6k^3$, every $n$-vertex graph $F$ with $\delta(F)\ge n-k$ contains every connected $n$-vertex graph $G$ with at most $n(1+1/(24k-12))$ edges and $\alpha'(G)\ge k-1$ as a spanning subgraph.
  • In this range the Ramsey number $r(G,K_{1,k})$ is exactly $n$ when $\alpha'(G)\ge k-1$, and in general it lies within $k-1-\alpha'$ of $n$, matching the earlier tree bound up to the parity term.
  • If additionally $\Delta(G)<n(1-1/(24k-12))$, the sparse spanning subgraph is guaranteed even without checking $\alpha'$, because the average-degree estimate forces $\alpha'\ge k-1$.
  • For $t$ disjoint stars, $r(G,tK_{1,k})\le n+t-1$ when $\alpha'(G)\ge k-1$ and $n\ge 28t^2k^3$, with equality obtained from the construction $K_{n-1}\cup K_{t-1}$.
  • The threshold on $n$ and the allowed edge density trade against each other: with density $n(1+1/(12k-12+24k/c))$ the proof works for smaller $n$, and in the limit $c\to0^+$ it covers all trees and unicyclic graphs on more than $2k^3+13k^2-40k+25$ vertices.

Reading between the lines

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

  • A reader extending these results should first check whether $\alpha'$ is monotone under the two reductions used in Theorem 5: deleting end-vertices or shortening a suspended path can in principle shrink $\alpha'(H)$ below $\alpha'(G)$, and the proof does not isolate this verification.
  • The complement encoding suggests a general template: $\delta(F)\ge n-k$ is equivalent to $\overline F$ being $K_{1,k}$-free, so the theorem says a $K_{1,k}$-free complement cannot avoid any sparse connected spanning graph above the threshold; the same strategy could be tried with other fixed graphs replacing the star.
  • The thresholds $6k^3$ and $28t^2k^3$ appear to be artifacts of the case analysis rather than tight bounds, since the concluding remark already exhibits a parameter tradeoff between $n$ and edge density.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 4 minor

Summary. The paper studies Ramsey numbers r(G,K1,k) for connected sparse graphs G on n vertices with at most n(1+ε) edges, and uses them to embed spanning subgraphs into graphs of minimum degree at least n−k. Theorem 4 gives a tight two-sided bound for r(G,K1,k) in terms of n, k and α′(G), generalizing the tree case of Erdős, Faudree, Rousseau and Schelp. Theorem 5 extends this to an upper bound for r(G,tK1,k). The proofs use a structural trichotomy for sparse graphs (Lemma 1, quoted from a preprint), a reduction lemma (Lemma 8) based on deleting or suppressing low-degree vertices, and case analysis depending on whether G has a long suspended path, a large matching of end-edges, or neither.

Significance. If the results are correct, Theorem 4 is a genuine and useful extension of the classic tree-star Ramsey bounds to sparse connected graphs, and Corollaries 1 and 2 give clean sufficient conditions for embedding sparse spanning subgraphs into graphs with prescribed minimum degree. The lower-bound construction in §2.1 is explicit and convincing, and Lemma 8's induction is sound: the reduction operation for a cut vertex of degree two preserves the degrees of its two neighbors, so the stated number of reductions can indeed be performed. The main caveats are that Theorem 4 depends essentially on the unproved structural lemma from a preprint, and that the proof of Theorem 5 does not track how the parameter α′ changes when the graph is reduced to H. The t-star generalization is therefore not established as written, although the underlying theorem may well be true after a repair.

major comments (2)
  1. [§3, Cases 1–3] The upper-bound proof for r(G,tK1,k) reduces G to a smaller connected graph H and then applies Lemma 9 or Theorem 4 using the original parameter α′=α′(G). In Case 1 the proof writes r(H,tK1,k) ≤ max{n−(t−1)k, n−(t−1)k+k−2−α′}+(t−1)(k+1); in Case 2 it writes r(H,K1,k) ≤ max{n−2tk+2, n−2tk+2+k−1−α′}; in Case 3 it writes r(H,K1,k) ≤ max{..., n−D+k−1−α′} with D=(t−1)k+k²−2k+2. In each display the parameter on the right is α′(G), but the lemmas invoked require the corresponding parameter of H. Neither equality of α′ nor an inequality controlling α′(H) is proved. Deleting leaves or shortening a suspended path can change α′ substantially; for instance, if G is the union of two adjacent vertices with L leaves at each vertex, then α′(G)=L, while deleting D leaves adjacent to one vertex lowers α′ to L−D. In Case 1 the displayed expression also appears off by one (the term k−2 should be k−1 to match Lemma 9). The theorem may still be true, but the proof as written leaves the t-star generalization unsupported.
  2. [§2.2, Case 3 and §3, Case 3] Both main theorems rely in their third case on Lemma 1, the sparse-graph trichotomy of Zhang and Chen [8]. This lemma is quoted from an unreferenced preprint and no proof is included. Since the case analysis is built directly on Lemma 1, the manuscript is not self-contained. The paper should either prove Lemma 1 in an appendix or state explicitly that Theorems 4 and 5 are conditional on [8]. This is a load-bearing dependency, not a cosmetic issue.
minor comments (4)
  1. [§2.1] In the lower-bound proof, the sentence 'Obviously, F contains no K1,k' is false for the graph F defined there; what is needed is that the complement of F contains no K1,k. Also, in the decomposition n+k−2−α′−β=tk+s, the parameter s should be allowed to be 0; the stated range '0<s≤k' excludes the case β=1 and remainder r=1.
  2. [§2.2, Case 1] The operation of shortening a suspended path is used without a formal definition. The proof later relies on the fact that shortening by d internal vertices reduces the edge count by exactly d; this should be stated explicitly, including the fact that an edge is added between the two remaining endpoints.
  3. [§4] The concluding remark asserts stronger versions of Theorems 4 and 5 for general constants c, with the phrase 'we can show', but no proof is supplied. These statements should be proved or explicitly labelled as conjectural.
  4. [Lemma 8] When n≤2k, the inequality e(G)≤n+2k/(2k+1) together with integrality gives e(G)≤n, but the text simply says that G has at most n edges; spelling out the integrality step would improve clarity.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the central self-cited Lemma 1 is an independent structural trichotomy, and the Theorem 5 alpha-prime tracking issue is a proof gap rather than a circular reduction.

full rationale

The derivation chain for Theorem 4 is self-contained except for one self-cited ingredient. In Case 3 of Theorem 4, the paper invokes Lemma 1 (Zhang and Chen [8]) to locate a vertex adjacent to many leaves when G has no long suspended path and no matching of end-edges. This is a load-bearing step, and the citation overlaps with the present authors, but Lemma 1 is a parameter-free structural statement about sparse graphs whose hypotheses do not mention Ramsey numbers, alpha-prime, or the target bound. Under the stated review rules, such a cited result counts as independent evidence rather than an imported conclusion, so it does not raise the circularity score. Lemma 8, which handles Cases 1 and 2, is proved in-paper by a reduction-and-reconstruction induction. Lemma 9 is derived directly from Theorem 4, and Theorem 5 proceeds by induction on t using Lemma 9, Theorem 4, and Lemma 1. There is, however, a substantive proof gap in Theorem 5: in each case the authors form a smaller connected graph H by shortening a suspended path or deleting end-vertices and then apply Theorem 4 or Lemma 9 with the original alpha' = alpha'(G), without proving alpha'(H) >= alpha'(G) or otherwise validating the bound. Shortening a path can decrease alpha' (e.g., P6 to P5 changes alpha' from 2 to 1), so the displayed bounds in Cases 1 and 3 are not established as written. This is a correctness/manuscript-support concern, not a circularity: no displayed inequality is identical to the theorem's conclusion by construction, and no fitted parameter is renamed as a prediction. Accordingly, no circular step is reported.

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

The paper introduces no new objects; it relies on standard theorems and one cited lemma from the same group.

assumptions (6)
  • standard math Hall's marriage theorem (Lemma 2)
    Used in Case 2 of Theorem 4 and Lemma 10 to find matchings.
  • standard math Chvatal's theorem r(T, Km) = (n-1)(m-1)+1 (Lemma 3)
    Used in Lemma 8's base case for trees.
  • standard math Burr's bound r(T, K1,k) <= n + k - 1 (Lemma 4)
    Used in Lemmas 6 and 8.
  • standard math Caro-Wei theorem
    Used in Remark 2 to bound independence numbers.
  • domain assumption Lemma 1 (Sparse Trichotomy of Zhang and Chen)
    Key structural lemma cited from the authors' own preprint [8]; not proven in this paper. If false, Case 3 of Theorems 4 and 5 fails.
  • ad hoc to paper alpha'(H) = alpha' after graph reductions
    Assumed in Theorem 5 Cases 1 and 2 without proof; not true in general, for instance shortening a path can change alpha'.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Minimum degree and sparse connected spanning subgraphs." pith.science (2026). https://pith.science/paper/BHGHBU3Q

@misc{pith2026250703264,
  author       = {Pith},
  title        = {Pith review of: Minimum degree and sparse connected spanning subgraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BHGHBU3Q}},
  note         = {Machine review of arXiv:2507.03264}
}
abstract

Let $G$ be a connected graph on $n$ vertices and at most $n(1+\epsilon)$ edges with bounded maximum degree, and $F$ a graph on $n$ vertices with minimum degree at least $n-k$, where $\epsilon$ is a constant depending on $k$. In this paper, we prove that $F$ contains $G$ as a spanning subgraph provided $n\ge 6k^3$, by establishing tight bounds for the Ramsey number $r(G,K_{1,k})$, where $K_{1,k}$ is a star on $k+1$ vertices. Our result generalizes and refines the work of Erd\H{o}s, Faudree, Rousseau, and Schelp (JCT-B, 1982), who established the corresponding result for $G$ being a tree. Moreover, the tight bound for $r(G,tK_{1,k})$ is also obtained.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Fan-goodness of sparse graphs

    math.CO 2025-07 conditional novelty 6.0 of 10

    Sparse connected graphs with at most n(1+1/(204k^3+126k^2)) edges are shown to have Ramsey number 2n-1 against fans F_k, with a similar result for multiple fans.

  2. Ramsey numbers of sparse graphs versus disjoint books

    math.CO 2025-07 conditional novelty 6.0 of 10

    For any large connected sparse graph G on n vertices, the Ramsey number r(G,tB_k) equals 2n+t-2, extending the tree-book result to all sparse graphs.

Reference graph

Works this paper leans on

8 extracted references · 4 canonical work pages · cited by 2 Pith papers

  1. [8]

    Zhang and Y

    Y. Zhang and Y. Chen, Trichotomy and tKm-goodness of sparse graphs, arXiv:2505.04142 [math.CO] (2025). 17

    arXiv 2025

  2. [1]

    Alon and J

    N. Alon and J. H. Spencer, The Probabilistic Method, John Wiley & Sons, 2016

    work page 2016

  3. [2]

    S.A. Burr, Generalized Ramsey Theory for Graphs–A Survey, Graphs and Combinatorics: Proceedings of the Capital Conference on Graph Theory and Combinatorics at the George Washington University, June 18–22, 1973, Springer Berlin Heidelberg, (1974), 52–75. 16

    work page 1974

  4. [3]

    S.A. Burr, P. Erd˝ os, R.J. Faudree, C.C. Rousseau, and R.H. Schelp, Ramsey numbers for the pair sparse graph-path or cycle, Trans. Amer. Math. Soc. 269 (1982), 501–512

    1982

  5. [4]

    Chv´ atal, Tree-complete graph Ramsey numbers, J

    V. Chv´ atal, Tree-complete graph Ramsey numbers, J. Graph Theory 1 (1977), 93–93

    1977

  6. [5]

    Erd˝ os, R.J

    P. Erd˝ os, R.J. Faudree, C.C. Rousseau, and R.H. Schelp, Graphs with certain families of spanning trees, J. Combin. Theory Ser. B 32 (1982), 162–170

    1982

  7. [6]

    Faudree, C.C

    R.J. Faudree, C.C. Rousseau, R.H. Schelp, and S. Schuster, Panarboreal graphs, Israel J. Math. 35 (1980), 177–185

    work page 1980

  8. [7]

    Hall, On representatives of subsets, J

    P. Hall, On representatives of subsets, J. London. Math. Soc. 1 (1935), 26–30

    work page 1935

Pith tools

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