This article is about mathematical matchings. For matching in the field of electronics, see: Impedance matching and Impedance bridging

In mathematical discipline of graph theory a matching or edge independent set for a graph is a set of edges without common vertices.

Definition

Given a graph G = (V,E) a matching M for G is a set of non-adjacent edges.

A maximum matching is the biggest matching possible.

The matching number for a graph is size of the maximum matching.

A perfect matching is a matching which covers all vertices of the graph. That is every vertex of the graph is incident to exactly one edge of the matching.

Examples

• A complete bipartite graph G_m,n has matching number min{m,n}

Notes

Some definitions also allow graphs with an odd number of vertices to have a perfect matching. These have exactly one unmatched vertex.

The marriage theorem provides a characterization of bipartite graphs which have a perfect matching and the Tutte theorem provides a characterization for arbitrary graphs.

There is a polynomial time algorithm (sometimes called Hungarian algorithm ) which, given a graph G, determines if G has a perfect matching and, if it has, finds a perfect matching.

A related problem is, given a graph G, determine the number of perfect matchings in G. This problem is #P Complete. For bipartite graphs, it can be approximately solved in polynomial time. That is, for any ε>0, there is a probabilistic polynomial time algorithm that determines the number of perfect matchings M with error at most εM, with high probability.

Properties

• for a connected graph G with n vertices the matching number + edge covering number = n (Tibor Gallai 1959)
• a graph with n vertices and a perfect matching has a matching number of n/2
• graphs with perfect matchings are 2-vertex colorable, that is they have a vertex chromatic number of 2

See also

• vertex independent set

References

• Gallai, Tibor "Über extreme Punkt- und Kantenmengen." Ann. Univ. Sci. Budapest, Eotvos Sect. Math. 2, 133-138, 1959.