The Furedi-Gyarfas-Simonyi Sharp Connected-Matching Conjecture
A connected matching in a graph is a matching whose edges are pairwise joined by at least one edge. Furedi, Gyarfas and Simonyi (2005) conjectured that every graph with independence number two on vertices has a connected matching of size . It was verified for by them and for by Chen and Deng, and Cambie showed it follows from Hadwiger's conjecture. Does every graph with on vertices have a connected matching of size ?
- Result
- Disproved(see note)
- Status
- Candidate (review pending)
- AI contribution
- AI-discovered
- Method
- Construction
- Field
- Extremal graph theory, matchings
- Posed by
- Zoltan Furedi, Andras Gyarfas and Gabor Simonyi, Connected matchings and Hadwiger's conjecture, Combin. Probab. Comput. 14 (2005)
- Year posed
- 2005
- Years open
- 21y
- Solved
- 2026-09-23
- Model
- Unreleased internal OpenAI model
- Vendor
- OpenAI
- Collaborators
- —
- Verification
- Unreviewed
- Publication
- Announced
- Collection
- OpenAI math release (October 2026), version fd4aeeb
- Significance
- 12 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
From Theorem 1.1 of the Hadwiger paper: deleting at most three vertices from its graphs gives graphs with on vertices whose connected-matching number stays below for all large , so the sharp conjecture fails. The weaker conjecture of the same authors, that for some absolute , is not settled: the bound leaves smaller coefficients open, and the paper says so.
What the AI did
Produced by an unreleased internal OpenAI model as part of an OpenAI evaluation on open research problems. The release README says the vast majority of results used one fixed procedure, averaging about three hours of ChatGPT Pro thinking compute per result; this result is not among the README's stated exceptions (the Riemann zeta zero-free region work and the Hodge conjecture for CM abelian varieties). The manuscript is authored as OpenAI with no human author named. The README also cautions that unformalized results could have issues.
Verification
No independent mathematician has checked this yet. Checked here: the historical section of the Hadwiger counterexample paper, which derives this disproof from its Theorem 1.1 in a short remark, read against the conjecture as cited (Furedi-Gyarfas-Simonyi 2005). Not refereed. The 7 October 2026 update added the Comparator challenge HadwigerCounterexample; its exists_counterexamples statement (read here) gives arbitrarily large -vertex graphs with and connected-matching number below . It does not state the conjecture's form (graphs on vertices with , matching size ); the short deletion step is not formalized, so the entry stays unreviewed. The disproof applies only for sufficiently large t.