---
tag: M063AZYXB5
kind: concept
name: Pairwise compatibility graph
sources:
  - wikipedia: en:69628781@r1364684176
    locator: Pairwise compatibility graph
    note: adopted
    mention: wikipedia://en/69628781
    sections: [Summary]
same_as:
  wikidata: Q111169660
  wikipedia: Pairwise compatibility graph
inventory: [9TBKXJ5CYB]
---

## Summary

In graph theory, a [[graph|00C0BR7D7H]] $G$ is a **pairwise compatibility graph** (PCG) if there exists a weighted tree $T$ and two non-negative real numbers $d_{min} \leq d_{max}$ such that each node $u'$ of $G$ has a one-to-one mapping with a leaf node $u$ of $T$ such that two nodes $u'$ and $v'$ are adjacent in $G$ if and only if the distance between $u$ and $v$ are in the interval $[d_{min}, d_{max}]$.