Saturation (graph theory)

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