Matching preclusion

Summary

In graph theory, a branch of mathematics, the matching preclusion number of a graph $G$, denoted $\mathrm{mp}(G)$, is the minimum number of edges whose deletion results in the elimination of all perfect matchings or near-perfect matchings (matchings that cover all but one vertex in a graph with an odd number of vertices). Matching preclusion measures the quality of a graph as a communications network topology for distributed algorithms that require each node of the distributed system to be matched with a neighboring partner node.