google-deepmind / google-deepmind/formal-conjectures

WOWII Conjecture 160 (source-corrected): complete Lean 4 proof — proposal to mark solved

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

Description

## Summary

The source-corrected Written on the Wall II Graph Conjecture 160 (#4423, corrected in #4443)
now has a complete Lean 4 proof of the exact corrected statement:

$$L_s(G) \ge \max_v \lambda(v) + \max_v T(v)\,\chi_{C_4}(G)$$

for finite nontrivial connected simple graphs, where $\chi_{C_4}(G)$ is the (not necessarily
induced) C4-free characteristic.

Immutable proof (theorem `conjecture160_proved`):
https://github.com/anagnorisis2peripeteia/formal-conjectures/blob/41d6835ad4325077c04122af476a08193110a933/WOWII160Proof.lean#L735

`#print axioms conjecture160_proved` reports exactly `propext`, `Classical.choice`,
`Quot.sound`; the pinned files contain no `sorry`, `admit`, `native_decide`, custom axiom,
or `unsafe` declaration.

## Relationship to existing work

- Depends on #4443 (@DomTheDeveloper's statement correction): the proof certifies the
corrected statement, so the status flip should land with or after it.
- Builds on #4565 (@kingcharlezz's Conjecture 2 proof), vendored byte-identical with credit
as the connected-seed foundation.
- #4569 (@vulnix0x4) independently announced an informal candidate proof of the same
corrected statement about three hours before this formalization first compiled in full;
the constructions differ, and this issue makes no claim of mathematical priority.

## Proposal

Flip `FormalConjectures/WrittenOnTheWallII/160.lean` to
`@[category research solved, ..., formal_proof using formal_conjectures at ""]`,
as in #4442 and #4565. A PR is attached.

Contributor guide

Open the contributing guide

Research direction

Open FormalConjectures/WrittenOnTheWallII/160.lean and compare its category annotation with the examples in #4442 and #4565. Use the pinned theorem proof link as the reference; done means the corrected conjecture is marked solved with the requested formal_proof metadata.

Written by the indexing model from the issue text.

Assessment

Domain
tooling
Issue type
Documentation
Difficulty
1/5
Estimated time
Under an hour
Activity status
Stale
Clarity
Clearly specified
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.