Perfect matching

A perfect matching in a graph is a set of edges that meets every vertex exactly once. It pairs all vertices without overlap.

Matching: A set of graph edges that share no endpoints. A perfect matching is a matching that covers every vertex.
Hall's marriage theorem: A theorem giving a necessary and sufficient condition for a bipartite graph to have a matching covering one side. When the two sides are equal in size, its condition characterizes perfect matchings.
Assignment problem: An optimization problem that assigns each worker or resource to exactly one task while minimizing total cost. A feasible complete assignment is a perfect matching in a bipartite graph.
Maximum matching: A matching with the greatest possible number of edges in a graph. A maximum matching need not cover every vertex, unlike a perfect matching.
P versus NP: The open computer-science question of whether every problem whose solutions can be verified efficiently can also be solved efficiently. Perfect matching is efficiently solvable, unlike many closely related matching-counting questions.
Graph theory: The mathematical study of vertices, edges, and their relationships. Perfect matching is a central property studied in graphs.
Tutte's theorem: A theorem characterizing graphs that contain a perfect matching through counts of odd components after vertex deletions. It gives the general existence criterion beyond bipartite graphs.
Stable marriage problem: A problem of pairing members of two groups according to preferences while preventing mutually preferred deviations. Its pairings are perfect matchings, though stability adds a preference constraint.
Maximal matching: A matching that cannot be enlarged by adding another edge without removing existing edges. Maximality is local and does not guarantee that every vertex is covered.
Permanent (mathematics): A matrix function defined like the determinant but without alternating signs in its permutation sum. For bipartite graphs, its value counts perfect matchings and is hard to compute generally.

Linked from 12 pages