An independent edge set (also called a matching) of a graph G is a subset of the edges such that no two edges in the subset share a vertex of G. The counts of independent edge sets of size k 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.

Hosoya index | independent set | independent vertex set | matching-generating polynomial | matching number | maximal independent edge set | maximum independent edge set