google-deepmind / google-deepmind/formal-conjectures

Formalize the counterexample to WOWII Conjecture 36

Open
#4,570 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Lean
Stars
1.3k
Forks
485
Avg merge
1d 20h
Merged PRs (30d)
327

Description

WOWII Conjecture 36 is already marked `research solved`; its docstring credits
Waller (October 2003) and records a counterexample with path number `5`, radius
`3`, and one diametrical pair. The theorem itself is still closed by `sorry`,
however, and the file does not give an explicit graph.

I have an explicit 10-vertex graph with those invariants. Its eight-vertex core
is a subdivided triangle together with two vertices adjacent to all three
triangle vertices; attaching one leaf to each of those two vertices gives the
counterexample. A finite Lean check establishes connectedness, radius `3`, a
unique diametrical pair, and largest induced-path order `5`, reducing the
proposed inequality to `6 ≤ 5`.

This is a formalization of a previously known disproof, not a claim of a new
mathematical disproof or of reproducing Waller's exact original graph.

## AI assistance disclosure

OpenAI Codex assisted with the finite graph search, independent invariant
checks, Lean proof development, and preparation of the contribution.

## Planned contribution

- [x] I plan to submit the follow-up pull request.
- [ ] This issue is up for grabs.

Contributor guide

Open the contributing guide

Research direction

Start with the existing WOWII Conjecture 36 theorem and its docstring, then inspect the proposed finite Lean check for the explicit graph. Done means the graph is represented formally, its connectedness, radius, unique diametrical pair, and path order are checked, and the theorem no longer uses `sorry`.

Written by the indexing model from the issue text.

Assessment

Domain
tooling
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.