google-deepmind / google-deepmind/formal-conjectures
Formalize the disproof of WOWII Conjecture 181
- Dominant language
- Lean
- Stars
- 1.3k
- Forks
- 485
- Avg merge
- 1d 20h
- Merged PRs (30d)
- 327
Description
## Summary
WOWII Conjecture 181 is currently listed as open. Under the source-faithful reading
`Ls(G) + b(G) ≥ α(G) + deg_avg(B(G²))`,
where `B(G²)` is the subgraph induced by the maximum-eccentricity vertices of `G²` and the average degree is measured in `G²`, the conjecture is false.
## Counterexample
Take the triangular graph `T(7) = L(K₇)`. The formally certified bounds and values are:
- `Ls(T(7)) ≤ 16`;
- `b(T(7)) = 6`;
- `α(T(7)) = 3`;
- `T(7)² = K₂₁`, so every square-periphery vertex has degree `20`.
Thus the proposed inequality would imply `16 + 6 ≥ 3 + 20`, i.e. `22 ≥ 23`.
The complete Lean 4 certificate is in the c5-k4 repository at immutable commit `3bfa33d`:
https://github.com/Kuberwastaken/c5-k4/blob/3bfa33d7470055a9a11d9ffde29186245dc3a329/lean/GraphConjecture181.lean#L1-L381
It compiles warning-clean with:
`lake env lean -DwarningAsError=true /path/to/c5-k4/lean/GraphConjecture181.lean`
`#print axioms` reports only `propext`, `Classical.choice`, `Lean.ofReduceBool`, `Lean.trustCompiler`, and `Quot.sound`; there is no `sorryAx` or project-specific axiom.
## Reading caveat
This counterexample depends on measuring average degree in `G²`, the graph whose peripheral subgraph is named. If the printed expression were instead interpreted as taking those vertices but measuring their degrees back in `G`, this witness would not refute that alternative statement: the right-hand side would be `3 + 10 = 13`.
## AI assistance disclosure
OpenAI Codex and delegated coding agents assisted with source interpretation, proof development, and verification. The submitter reviewed the mathematical statement, counterexample, and generated Lean artifact and takes responsibility for the submission.
Contributor guide
Research direction
Start with the cited c5-k4/lean/GraphConjecture181.lean certificate at commit 3bfa33d and run the supplied Lean command with warningAsError enabled. Check the formal statement's interpretation of average degree against the issue text and verify the certificate's reported axioms. Done means the disproof is formally verified and the conjecture's status or record is updated accordingly.
Written by the indexing model from the issue text.
Assessment
- Domain
- tooling
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100