Saturation (graph theory)

{{Multiple issues|

{{one source |date=April 2024}}

{{Unfocused|date=November 2024}}

}}

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.For some results, see https://faculty.math.illinois.edu/~west/regs/saturate.html.

In matching theory, there is a different definition.

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