Perfect matching

Perfect matching is a concept in graph theory, a branch of discrete mathematics. A perfect matching is a matching in which every vertex of the graph is connected to exactly one edge of the matching. In other words, it is a set of edges that covers every vertex of the graph exactly once.

Definition

In a given graph \( G = (V, E) \), a matching \( M \subseteq E \) is called a perfect matching if every vertex \( v \in V \) is incident to exactly one edge in \( M \). This implies that the graph must have an even number of vertices for a perfect matching to exist.

Properties

• A graph with a perfect matching must have an even number of vertices.
• If a graph has a perfect matching, then it is a 1-factor.
• The permanent of the adjacency matrix of a bipartite graph can be used to count the number of perfect matchings in the graph.

Examples

• In a complete graph \( K_{2n} \), there are \((2n-1)!!\) perfect matchings.
• In a bipartite graph \( K_{n,n} \), there are \( n! \) perfect matchings.

Algorithms

Several algorithms exist to find a perfect matching in a graph:

• The Hungarian algorithm is used to find a perfect matching in a bipartite graph.
• The Blossom algorithm is used to find a perfect matching in general graphs.

Applications

Perfect matchings have applications in various fields such as:

• Network design
• Scheduling
• Resource allocation
• Molecular chemistry, where they are used to model chemical structures.

Related Concepts

• Matching (graph theory)
• Maximum matching
• Stable marriage problem
• Hall's marriage theorem
• Tutte's theorem

See Also

• Graph theory
• Discrete mathematics
• Algorithm