WOWII Conjecture 72: Two induced trees pin down tree()
For a connected graph , let tree() (order of a largest induced tree), average eccentricity, and maximum independence number of a neighbourhood. Then
(The evenly-divided reading of the conjecture holds; a stronger reading that divides only by three is false.)
- Result
- Proved(see note)
- Status
- Candidate (review pending)
- AI contribution
- AI-discovered
- Method
- Argument
- Field
- Graph theory (induced trees / graph invariants)
- Posed by
- Ermelinda DeLaViña (Graffiti.pc / Written on the Wall II)
- Year posed
- 2001
- Years open
- 25y
- Solved
- 2026-07-23
- Model
- GPT 5.6 Sol
- Vendor
- OpenAI
- Collaborators
- —
- Verification
- Site-confirmed
- Publication
- Announced
- Significance
- 5 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
The evenly-divided reading of WOWII Conjecture 72 holds:
where tree() (order of a largest induced tree), average eccentricity and maximum neighbourhood independence number.
A stronger reading that divides only by three is false. The argument rests on two elementary observations (a diametral path is chordless and therefore induces a tree on vertices; a maximum independent set in a neighbourhood induces a star on vertices). The original conjecture’s precise wording is not yet pinned in a public formal repository, so statement fidelity remains to be audited.
What the AI did
The model was given a short prompt (copied from a successful earlier run on a different WOWII conjecture) and asked to find a solution or counterexample to an open conjecture of its choosing. It selected WOWII Conjecture 72, produced the two-lemma argument (diametral path induces a tree on vertices; maximum independent neighbourhood induces a star on vertices), derived the bound , and explicitly distinguished the evenly-divided reading (true) from the stronger reading that divides only by three (false). The human then posted the diagram and commentary.
Verification
Re-derived in full by this site on 17 August 2026 - the argument is elementary and correct, and short enough to state: a shortest path between two vertices at maximum distance D is induced, so it induces a path (a tree) on D+1 vertices, giving tree(G) >= D+1 >= A+1 since average eccentricity is at most D; a maximum independent set in a neighbourhood plus its centre induces a star on L+1 vertices, giving tree(G) >= L+1; hence A + L <= 2*tree(G) - 2, and ceil((A+L)/3) <= tree(G) follows by integrality. The stronger reading (dividing only L by three) fails on the claimed counterexample family. What keeps this Candidate is not the mathematics but the statement: Conjecture 72's canonical wording is not publicly pinned (no formal statement exists in the Formal Conjectures repository), so which reading DeLaViña intended is unconfirmed, and the X post plus transcript is the only artifact. Site-confirmed records this site's independent re-derivation of the proved reading.
Source
Submitted by QuietFerret326 on