VibeMathedMath problems solved with AI
Sign in

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 4t−14t-1 vertices has a connected matching of size tt. It was verified for t≤17t\le17 by them and for t≤22t\le22 by Chen and Deng, and Cambie showed it follows from Hadwiger's conjecture. Does every graph GG with α(G)=2\alpha(G)=2 on 4t−14t-1 vertices have a connected matching of size tt?

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 adc7f12
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 α=2\alpha=2 on 4t−14t-1 vertices whose connected-matching number stays below tt for all large tt, so the sharp conjecture fails. The weaker conjecture of the same authors, that cm(G)≥c0∣V(G)∣\mathrm{cm}(G)\ge c_0|V(G)| for some absolute c0>0c_0>0, is not settled: the bound cm<m/100\mathrm{cm}<m/100 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. No Lean result. The disproof applies only for sufficiently large t.

Sources

Changelog1 change

Discussion