The independence number is at most the annihilation number

lax-421170·formalized by Samuel Varchol @rivalxy·registered·created ·GitHub @900f1ef·Lean v4.33.0 epoch · mathlib db584cd6d46c

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this submission may be incorrect.

No flags have been submitted.

    Community review

    Flag this submission

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    Abstract

    Let GG be a finite simple graph with mm edges and degrees d1≤d2≤⋯≤dnd_1 \le d_2 \le \dots \le d_n in nondecreasing order. The annihilation number a(G)a(G) is the largest kk such that ∑i=1kdi≤m\sum_{i=1}^{k} d_i \le m. We formalize the bound α(G)≤a(G)\alpha(G) \le a(G) on the independence number, due to Pepper. The proof observes that the vertex degrees of an independent set sum to at most mm, since every edge has at most one endpoint in the set, and that the kk smallest degrees sum to at most the degrees of any kk vertices.

    Concepts

    Concept map
    2 concepts
    100%
    Proven claimDefinitionThis submissionA → B: B builds on A

    Proofs

    Proof networkview on GitHub

    100%
    assumptions conclusionProven claimClaim from this submissionProof — open large view for details
    Proof list

    Lean sources for these proofs: proofs/ on GitHub

    Proof code is not displayed; the archive records each proof's checked relationship between claims.

    Related submissions

    No other submission in the archive builds on this one, and this one builds on none.

    Cite this

    This is only the formalizers. The authors of the formalized results may be different (see References).

    @misc{lax-421170,
      author = {Samuel Varchol},
      title = {The independence number is at most the annihilation number},
      year = {2026},
      howpublished = {Lax Archive, lax-421170},
      url = {https://laxarchive.org/lax-421170/},
    }

    References

    1. Ryan Pepper. Binding Independence. University of Houston, 2004.
    2. C. E. Larson and R. Pepper. Graphs with Equal Independence and Annihilation Numbers. The Electronic Journal of Combinatorics 18(1):P180, 2011.

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…