 TOPICS # Independent Edge Set

An independent edge set (also called a matching) of a graph is a subset of the edges such that no two edges in the subset share a vertex of (Skiena 1990, p. 219). The counts of independent edge sets of size in a graph are encoded through its matching-generating polynomial.

The number of independent edge sets in a graph is sometimes called the Hosoya index.

An independent edge set of maximum size is called a maximum independent edge set, and an independent edge set that cannot be expanded to another independent edge set by addition of any other edge in the graph is called a maximal independent edge set.

A maximum independent edge set can be computed in the Wolfram Language using FindIndependentEdgeSet[g].

The size of the largest independent edge set (i.e., of any maximum independent edge set) in a graph is known as its matching (or edge independence) number.

Hosoya Index, Independent Set, Independent Vertex Set, Matching Number, Matching-Generating Polynomial, Maximal Independent Edge Set, Maximum Independent Edge Set

## Explore with Wolfram|Alpha More things to try:

## Cite this as:

Weisstein, Eric W. "Independent Edge Set." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/IndependentEdgeSet.html