Saturation (graph theory)

From Wikipedia, the free encyclopedia

This article does not cite any references or sources. (August 2006)
Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.

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$ .