A lower bound on the saturation number and a strengthening for
triangle-free graphs
A lower bound on the saturation number and a strengthening for
triangle-free graphs
The saturation number $\operatorname{sat}(n, H)$ of a graph $H$ and positive integer $n$ is the minimum size of an $n$-vertex graph which does not contain a subgraph isomorphic to $H$ but to which the addition of any edge creates such a subgraph. Erd\H{o}s, Hajnal, and Moon first studied saturation numbers …