Graffiti Conjecture 6

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

Result: Disproved (Infinite family of counterexamples; mathematical argument internally checked, with external verification and novelty review pending.)
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 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 $\alpha(T_s)=2s+5,\qquad r(T_s)=2s+4,\qquad \rho(T_s)=3.$ Since $\ln 3>1$ , it follows that $\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

Graffiti Conjecture 6 Counterexample

Submitted by Lamp

Graffiti Conjecture 6

What the AI did

Verification

Source

Discussion