Saturation (graph theory)

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

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

See also

• Hall's marriage theorem
• Bipartite matching