Saturation (graph theory)

Given a graph $H$, another graph $G$ is $H$-saturated if $G$ does not contain a (not necessarily induced) copy of $H$, but adding any edge to $G$ it does. The function $sat(n,H)$ is the minimum number of edges an $H$-saturated graph $G$ on $n$ vertices can have.

In matching theory, there is a different definition. Let $G(V,E)$ be a graph and $M$ a matching in $G$. A vertex $v\in V(G)$ is said to be saturated by $M$ if there is an edge in $M$ incident to $v$. A vertex $v\in V(G)$ with no such edge is said to be unsaturated by $M$. We also say that $M$ saturates $v$.

See also

• Hall's marriage theorem
• Bipartite matching