Saturation (graph theory)
Encyclopedia
Let 
be a graph
and
a matching in 
. A vertex 
is said to be saturated by 
if there is an edge in 
incident to 
. A vertex 
with no such edge is said to be unsaturated by 
. We also say that 
saturates 
.
be a graphGraph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
and
a matching in . A vertex is said to be saturated by if there is an edge in incident to . A vertex with no such edge is said to be unsaturated by . We also say that saturates .