Saturation (graph theory) explained

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.^[1]

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

Notes and References

1. For some results, see https://faculty.math.illinois.edu/~west/regs/saturate.html.