Pith. sign in

REVIEW 1 minor 27 references

Ramsey-finiteness for graph pairs: A complete solution to the Burr-Erd\H{o}s-Faudree-Schelp conjectures

T0 review · 0 major / 1 minor · reviewed 2026-05-10 · grok-4.3

Challenge this review Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The set of Ramsey-minimal graphs for a pair (G,H) is finite precisely when the pair belongs to the matchings family, the odd-stars-with-matchings family, or Faudree's star-forest family.

desk verdict This paper proves the two 1981 conjectures and gives the correct necessary-and-sufficient condition for Ramsey-finite graph pairs. read the letter →

arxiv 2604.17356 v2 submitted 2026-04-19 math.CO

Yaping Mao This is my paper · ORCID
classification math.CO
keywords Ramsey-minimalgraphsgraphpairsRamsey-finitenessBurr-ErdősconjecturesstarforestsmatchingsoddstarsRamseytheory
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 paper proves that Ramsey-finiteness for graph pairs is preserved when disjoint matchings are adjoined to either graph. It establishes that (G,H) yields infinitely many non-isomorphic Ramsey-minimal graphs unless both G and H are odd stars or one of them contains a K2 component. The work supplies the exact necessary-and-sufficient condition: the only finite cases are the two families already covered by the conjectures plus the additional star-forest pairs identified by Faudree. A reader would care because the result gives a definitive partition of all graph pairs into those with finitely many minimal witnesses and those with infinitely many.

What carries the argument

The preservation of Ramsey-finiteness under adjoining disjoint matchings, used together with exhaustive case analysis that rules out all other graph configurations.

What would settle it

A concrete counterexample would be any pair (G,H) that is neither both odd stars, nor contains a K2 component in the stated way, nor belongs to the matching or Faudree star-forest families, yet still has only finitely many non-isomorphic Ramsey-minimal graphs.

Watch

Extended reading notes

Core claim

For finite graphs G and H, the set RR(G,H) of isomorphism classes of Ramsey-minimal graphs for the pair (G,H) is finite if and only if the pair falls into the matching case, the odd-star-with-matchings case, or Faudree's star-forest family. This confirms both 1981 conjectures and corrects the earlier proposed characterization by showing that no other families produce only finitely many Ramsey-minimal graphs.

Load-bearing premise

The combinatorial case analysis must exhaustively cover every possible pair of graphs without leaving an undetected exceptional family.

Editorial extensions

If this is right

  • Adjoining a disjoint matching to G or to H leaves the finiteness or infiniteness of RR(G,H) unchanged.
  • Any pair in which neither graph is an odd star and neither contains a K2 component is Ramsey-infinite.
  • Faudree's star-forest family supplies the only additional finite pairs beyond the matching and odd-star cases.
  • All other graph pairs produce infinitely many distinct Ramsey-minimal graphs.

Reading between the lines

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

  • The classification makes it feasible to enumerate all finite Ramsey-minimal graphs for any small pair in the three exceptional families.
  • Most pairs of graphs therefore admit infinitely many minimal witnesses for the monochromatic embedding property.
  • The same preservation mechanism may extend to questions about the growth rate of the number of minimal graphs when the pair is infinite.
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, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 1 minor

Summary. The manuscript proves two 1981 conjectures of Burr, Erdős, Faudree, Rousseau, and Schelp on Ramsey-finiteness for graph pairs (G, H). It establishes that Ramsey-finiteness is preserved by adjoining disjoint matchings and that (G, H) is Ramsey-infinite unless both graphs are odd stars or one graph has a K₂ component. It further supplies the correct necessary-and-sufficient characterization of Ramsey-finite pairs, identifying the matching case, the odd-star-with-matchings case, and Faudree's star-forest family as the only finite instances.

Significance. If the proofs are correct, the work delivers a complete classification of when the set of Ramsey-minimal graphs RR(G, H) is finite, resolving long-standing open problems in graph Ramsey theory. The explicit combinatorial constructions, case distinctions on matchings and star components, and correction of Burr's earlier stronger characterization constitute a substantial advance; the arguments use only standard graph-theoretic tools without free parameters or circular reductions.

minor comments (1)
  1. [Abstract] The abstract is concise but dense; a single sentence outlining the main proof strategy (partitioning into matching, odd-star, and star-forest regimes) would improve accessibility without lengthening the text appreciably.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, recognition of the significance of resolving the Burr-Erdős-Faudree-Schelp conjectures, and recommendation to accept the manuscript.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity

full rationale

The manuscript is a direct combinatorial proof of two 1981 conjectures on Ramsey-finiteness for graph pairs, proceeding via explicit case analysis on matchings, odd-star components, and star-forest structures. No parameters are fitted, no predictions are derived from subsets of the same data, and no load-bearing step reduces to a self-citation or self-definition. The central claims rest on standard graph-theoretic constructions and exhaustive partitioning that are independent of the target results. This is the normal, self-contained case for a pure-mathematics resolution of an open conjecture.

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

The paper relies on standard axioms of graph theory and combinatorics such as the definitions of graphs, edges, colorings, and Ramsey-minimality. No free parameters, invented entities, or non-standard axioms are mentioned in the abstract. A full ledger cannot be completed without the manuscript.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Ramsey-finiteness for graph pairs: A complete solution to the Burr-Erd\H{o}s-Faudree-Schelp conjectures." pith.science (2026). https://pith.science/paper/2604.17356

@misc{pith2026260417356,
  author       = {Pith},
  title        = {Pith review of: Ramsey-finiteness for graph pairs: A complete solution to the Burr-Erd\Hos-Faudree-Schelp conjectures},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2604.17356}},
  note         = {Machine review of arXiv:2604.17356}
}
abstract

For finite graphs $G$ and $H$, let $\RR(G,H)$ denote the isomorphism classes of Ramsey-minimal graphs for $(G,H)$. We prove two 1981 conjectures of Burr, Erd\H{o}s, Faudree, Rousseau, and Schelp: Ramsey-finiteness is preserved by adjoining disjoint matchings, and $(G,H)$ is Ramsey-infinite unless both graphs are odd stars or one graph has a $K_2$ component. We also replace Burr's stronger 1979 survey characterization by the correct necessary-and-sufficient form: apart from the matching case and the odd-star-with-matchings case, the only additional finite pairs are Faudree's star-forest family.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages

  1. [1]

    Bamberg, A

    J. Bamberg, A. Bishnoi, and T. Lesgourgues,The minimum degree of Ramsey-minimal graphs for cliques, Bull. London Math. Soc.54(2022), 1827–1838

    work page 2022

  2. [2]

    Bollobás, J

    B. Bollobás, J. Donadelli, Y. Kohayakawa, and R. H. Schelp,Ramsey minimal graphs, J. Braz. Comput. Soc.7(2001), 27–37

    work page 2001

  3. [3]

    S. A. Burr, P. Erdős, and L. Lovász,On graphs of Ramsey type, Ars Combin.1(1976), 167–190

    work page 1976

  4. [4]

    S. A. Burr, R. J. Faudree, and R. H. Schelp,On graphs with Ramsey-infinite blocks, European J. Combin.6(1985), 129–132

    work page 1985

  5. [5]

    Borowiecki, M

    M. Borowiecki, M. Hałuszczak, and E. Sidorowicz,On Ramsey minimal graphs, Discrete Math.286(2004), 37–43

    work page 2004

  6. [6]

    Borowiecka-Olszewska and M

    M. Borowiecka-Olszewska and M. Hałuszczak,On Ramsey(K1,m,G)-minimal graphs, Discrete Math.313(2013), 1843–1855

    work page 2013

  7. [7]

    Borowiecki, I

    M. Borowiecki, I. Schiermeyer, and E. Sidorowicz,Ramsey(K1,2, K3)-minimal graphs, Electron. J. Combin.12(2005), Paper R20, 15 pp. 10 YAPING MAO

    work page 2005

  8. [8]

    S. A. Burr, P. Erdős, R. J. Faudree, and R. H. Schelp,A class of Ramsey-finite graphs, Proc. 9th Southeastern Conf. on Combinatorics, Graph Theory and Computing, 1978, pp. 171–180

    work page 1978

Show all 27 references
  1. [9]

    S. A. Burr, P. Erdős, R. J. Faudree, and R. H. Schelp,Ramsey minimal graphs for the pair star, connected graph, Studia Sci. Math. Hungar.15(1980), 265–273

    1980

  2. [10]

    S. A. Burr, P. Erdős, R. J. Faudree, C. C. Rousseau, and R. H. Schelp,Ramsey- minimal graphs for matchings, inThe Theory and Applications of Graphs(Kalamazoo, Mich., 1980), Wiley, New York, 1981, pp. 159–168

    1980

  3. [11]

    S. A. Burr, P. Erdős, R. J. Faudree, C. C. Rousseau, and R. H. Schelp,Ramsey-minimal graphs for forests, Discrete Math.38(1982), 23–32

    1982

  4. [12]

    S. A. Burr, P. Erdős, R. J. Faudree, C. C. Rousseau, and R. H. Schelp,Ramsey-minimal graphs for star-forests, Discrete Math.33(1981), 227–237

    1981

  5. [13]

    S. A. Burr,A survey of noncomplete Ramsey theory for graphs, inTopics in Graph Theory, Ann. New York Acad. Sci.328(1979), 58–75

    1979

  6. [14]

    Christoph, A

    M. Christoph, A. Martinsson, R. Steiner, and Y. Wigderson,Resolution of the Kohayakawa–Kreuter conjecture, Proc. Lond. Math. Soc.130(2025), e70013

    2025

  7. [15]

    Faudree,Ramsey minimal graphs for forests, Ars Combin.31(1991), 117–124

    R. Faudree,Ramsey minimal graphs for forests, Ars Combin.31(1991), 117–124

    1991

  8. [16]

    Łuczak,On Ramsey minimal graphs, Electron

    T. Łuczak,On Ramsey minimal graphs, Electron. J. Combin.1(1994), Research Paper 4, 4 pp

    1994

  9. [17]

    J. Fox, A. Grinshpun, A. Liebenau, Y. Person, and T. Szabó,On the minimum degree of Ramsey-minimal graphs for multiple colours, J. Combin. Theory Ser. B120(2016), 64–82

    2016

  10. [18]

    H. Hàn, V. Rödl, and T. Szabó,Vertex Folkman numbers and the minimum degree of Ramsey-minimal graphs, SIAM J. Discrete Math.32(2018), 826–838

    2018

  11. [19]

    Kohayakawa and B

    Y. Kohayakawa and B. Kreuter,Threshold functions for asymmetric Ramsey properties involving cycles, Random Structures Algorithms11(1997), 245–276

    1997

  12. [20]

    Kuperwasser and W

    E. Kuperwasser and W. Samotij,The list-Ramsey threshold for families of graphs, Combin. Probab. Comput.33(2024), 829–851

    2024

  13. [21]

    Mousset, R

    F. Mousset, R. Nenadov, and W. Samotij,Towards the Kohayakawa–Kreuter conjecture on asymmetric Ramsey properties, Combin. Probab. Comput.29(2020), 943–955

    2020

  14. [22]

    Nešetřil and V

    J. Nešetřil and V. Rödl,On Ramsey minimal graphs, Colloq. Internationaux C.N.R.S. 260(1978), 307–308

    1978

  15. [23]

    Nešetřil and V

    J. Nešetřil and V. Rödl,The structure of critical Ramsey graphs, Acta Math. Acad. Sci. Hungar.32(1978), 295–300

    1978

  16. [24]

    Rödl and A

    V. Rödl and A. Ruciński,Threshold functions for Ramsey properties, J. Amer. Math. Soc.8(1995), 917–942

    1995

  17. [25]

    Rödl and M

    V. Rödl and M. Siggers,On Ramsey minimal graphs, SIAM J. Discrete Math.22 (2008), 467–488

    2008

  18. [26]

    Szabó, P

    T. Szabó, P. Zumstein, and S. Zürcher,On the minimum degree of Ramsey-minimal graphs, J. Graph Theory64(2010), 150–164

    2010

  19. [27]

    Wijaya, E

    K. Wijaya, E. T. Baskoro, H. Assiyatun, and D. Suprijanto,On Ramsey(mK2, H)- minimal graphs, Graphs Combin.33(2017), 233–243. Academy of Plateau Science and Sustainability, and School of Mathematics and Statistics, Qinghai Normal University, Xining 810008, China Email address:...

    2017

Pith tools

Reviewed May 10, 2026 · model on record in the stance chip above.