Saturation (graph theory)

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

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

See also

• Hall's marriage theorem
• Bipartite matching