---
tag: SSC5WGWKW9
kind: concept
name: Matching preclusion
aliases: [preclude]
sources:
  - wikipedia: en:27970912@r1322814211
    locator: Matching preclusion
    note: adopted
    mention: wikipedia://en/27970912
    sections: [Summary]
same_as:
  wikidata: Q17135100
  wikipedia: Matching preclusion
inventory: [PJ2TW38TB7]
---

## 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|05ZPH8KF9K]] 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.