google-deepmind / google-deepmind/formal-conjectures

Formalize the disproof of WOWII Conjecture 181

Open
#4,905 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

## 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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.