A proof for Problems 5 and 6 of "Extremizing antiregular graphs by modifying total σ-irregularity", with a Lean 4 formalization
We prove that for every n, every simple graph G on n vertices and every nondecreasing concave function φ with φ(0) = 0, the sum of φ(|d(u) - d(v)|) over pairs of vertices is at most its value on the antiregular graphs. For φ(k) = k^c with 0 < c ≤ 1 this answers Problems 5 and 6 of Knor, Škrekovski, Filipovski and Dimitrov, "Extremizing antiregular graphs by modifying total σ-irregularity" (Appl. Math. Comput. 490, 2025; arXiv:2411.01530) in the affirmative. This work was carried out with AI language models (Anthropic Claude) under the author's direction. The models selected the problem from the paper, ran the computer checks and produced the proof. The author has no academic training in mathematics. The full argument is formalized in Lean 4 with Mathlib; the file compiles without sorry and depends only on the axioms propext, Classical.choice and Quot.sound. Uniqueness of the maximizers is not claimed. The author has not found this result in the literature but cannot rule out prior work.
Authors
- Arturo Abreu
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-12
- DOI
- https://doi.org/10.5281/zenodo.24178745
- Primary Topic
- Graph theory and applications
- Type
- preprint