VibeMathedMath problems solved with AI
Sign in

Graffiti Conjecture 6

Every finite connected simple graph G satisfies
α(G)≥r(G)+ln⁡(ρ(G)),\alpha(G)\ge r(G)+\ln(\rho(G)),
where α(G)\alpha(G) is the independence number, r(G)r(G) is the radius, and ρ(G)\rho(G) is the minimum number of pairwise vertex-disjoint paths whose vertices cover V(G)V(G).

Result
Disproved(see note)
Status
Candidate (review pending)
AI contribution
AI-discovered
Method
Construction
Field
Graph theory
Posed by
Graffiti, reported by Ermelinda DeLaViña, Siemion Fajtlowicz, and Bill Waller
Year posed
2002
Years open
24y
Solved
2026-07-30
Model
GPT-5.6 Thinking
Vendor
OpenAI
Collaborators
Jackson (prompter)
Verification
Unreviewed
Publication
Announced
Significance
5 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Infinite family of counterexamples; mathematical argument internally checked, with external verification and novelty review pending.

What the AI did

GPT-5.6 Thinking produced and checked an infinite family of counterexamples. For each integer s >= 0, it considered a tree T_s formed from the path v_0v_1...v_{4s+7} by attaching leaves at v_{2s+2} and v_{2s+5}. It proved that
α(Ts)=2s+5,r(Ts)=2s+4,ρ(Ts)=3.\alpha(T_s)=2s+5,\qquad r(T_s)=2s+4,\qquad \rho(T_s)=3.
Since ln⁡3>1\ln 3>1, it follows that
α(Ts)=2s+5<2s+4+ln⁡3=r(Ts)+ln⁡ρ(Ts).\alpha(T_s)=2s+5<2s+4+\ln 3=r(T_s)+\ln\rho(T_s).
Thus every T_s is a counterexample, disproving the conjecture and providing infinitely many counterexamples. The AI also audited the final proof line by line.

Verification

The proof was checked line by line by GPT-5.6 Thinking. The radius, independence number, perfect matching, and path-covering number arguments were separately recomputed, including the smallest case s=0. The proof appears mathematically valid, but as of 2026-07-30 it has not been independently verified by an external graph theorist, a formal proof assistant, or peer review.

Source

Submitted by Lamp on

Changelog3 changes

Discussion1

ZestyWombat85413 Aug 2026, 00:26 UTC· edited

We built a checker that computes α, r, and ρ from scratch — from the mathematical definitions, not from the claim's formulas — and tested every tree T_s from s = 0 to s = 30.

Each one has α = 2s+5, r = 2s+4, ρ = 3, and violates the conjecture: α < r + ln ρ. The critical comparison (e < 3) is decided exactly by SymPy — no floating-point arithmetic. α and ρ were each computed two independent ways (subset enumeration cross-checked against tree DP for α; edge-subset brute force cross-checked against degree-constrained DP for ρ); r by all-source BFS. Four control graphs that should satisfy the conjecture were correctly not flagged.

The s = 0 counterexample turns out to be the tree in Figure 1 of the paper that stated the conjecture (DeLaViña–Fajtlowicz–Waller, DIMACS vol. 69, 2005, p. 4). The authors drew it as an equality example for Conjectures 4 and 5 — and didn't notice it breaks Conjecture 6 three pages later. No prior resolution was found in an arXiv sweep, OpenAlex citation search (one citing work, off-topic), or the authors' later papers, one of which still calls the weaker Conjecture 5 open.

A second reviewer independently re-ran the checker (byte-identical output), re-derived the proof from the source, and agreed.

Evidence: https://gist.github.com/ZestyWombat854/59a424d198b461fdb41fe6f5a6902600

Edit 2026-08-14: the evidence now also lives in a CI-backed repo — https://github.com/ZestyWombat854/graffiti-conjecture-6-verification — which supersedes and pins the gist above (kept exactly as reviewed); CI re-runs the checker and confirms byte-identical results on every push.

0