Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Perfect matching
Summary
In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph G = (V, E), a perfect matching in G is a subset M of edge set E, such that every vertex in the vertex set V is adjacent to exactly one edge in M.
A perfect matching is also called a 1-factor; see Graph factorization for an explanation of this term. In some literature, the term complete matching is used.
Every perfect matching is a maximum-cardinality matching, but the opposite is not true. For example, consider the following graphs:
In graph (b) there is a perfect matching (of size 3) since all 6 vertices are matched; in graphs (a) and (c) there is a maximum-cardinality matching (of size 2) which is not perfect, since some vertices are unmatched.
A perfect matching is also a minimum-size edge cover. If there is a perfect matching, then both the matching number and the edge cover number equal / 2.
A perfect matching can only occur when the graph has an even number of vertices. A near-perfect matching is one in which exactly one vertex is unmatched. This can only occur when the graph has an odd number of vertices, and such a matching must be maximum. In the above figure, part (c) shows a near-perfect matching. If, for every vertex in a graph, there is a near-perfect matching that omits only that vertex, the graph is also called factor-critical.
Hall's marriage theorem provides a characterization of bipartite graphs which have a perfect matching.
The Tutte theorem provides a characterization for arbitrary graphs.
A perfect matching is a spanning 1-regular subgraph, a.k.a. a 1-factor. In general, a spanning k-regular subgraph is a k-factor.
A spectral characterization for a graph to have a perfect matching is given by Hassani Monfared and Mallik as follows: Let be a graph on even vertices and be distinct nonzero purely imaginary numbers. Then has a perfect matching if and only if there is a real skew-symmetric matrix with graph and eigenvalues .
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.