The independence number is at most the annihilation number
No public endorsements yet.
Loading review…
Sign in with ORCIDAbstract
Let be a finite simple graph with edges and degrees in nondecreasing order. The annihilation number is the largest such that . We formalize the bound on the independence number, due to Pepper. The proof observes that the vertex degrees of an independent set sum to at most , since every edge has at most one endpoint in the set, and that the smallest degrees sum to at most the degrees of any vertices.
Concepts
Concept map
Proofs
Proof networkview on GitHub
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
- Ryan Pepper. Binding Independence. University of Houston, 2004.
- 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.
0 comments