Graph saturation measures the smallest size of a graph that avoids a specified subgraph but loses that property
whenever a missing edge is added. A simple
graph 
is 
-saturated
if it contains no subgraph isomorphic to 
and adding any missing edge
creates such a subgraph. The saturation number 
is the minimum number of edges
in an 
-vertex
-saturated graph.
For example, every star graph on 
vertices is 
-saturated. More generally,
 |
An extremal construction is the graph join of 
and an empty
graph on 
vertices (Erdős et al. 1964).
For an edge-ordered graph, saturation also depends on where the new edge is inserted in the order. Bošković and Keszegh (2026) exhibit superlinear saturation functions when every insertion position must create an order-preserving copy of the forbidden edge-ordered graph.
