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.