# Matching

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

 Contents

## 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.

## 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. There is also a polynomial time algorithm to find a maximum matching in a graph.

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.

## References

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

• Art and Cultures
• Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
• Space and Astronomy