Maximal Independent Edge Set

A maximal independent edge set of a graph is an independent edge set that cannot be expanded to another independent edge set by addition of any edge in the graph.

Note that a maximal independent edge set is not equivalent to a maximum independent edge set, which is an independent edge set containing the largest possible number of edges among all independent edge sets. A maximum independent edge set is always maximal, but the converse does not hold.

A maximal independent edge set of a graph can be computed in the Wolfram Language using FindIndependentEdgeSet[g].

See also

Blossom Algorithm, Hungarian Maximum Matching Algorithm, Independent Edge Set, Matching, Maximal Independent Vertex Set, Maximal Set, Maximum Independent Edge Set, Perfect Matching

Explore with Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Maximal Independent Edge Set." From MathWorld--A Wolfram Web Resource.

Subject classifications