---
tag: 2MWTBETCWQ
kind: concept
name: Cluster graph
sources:
  - wikipedia: en:50931136@r1368893523
    locator: Cluster graph
    note: adopted
    mention: wikipedia://en/50931136
    sections: [Summary]
same_as:
  wikidata: Q24892498
  wikipedia: Cluster graph
inventory: [NMXJ11ZPB6]
---

## Summary

In graph theory, a branch of mathematics, a **cluster graph** is a [[graph|00C0BR7D7H]] formed from the disjoint union of [[complete graphs|03WKB2H474]]. Equivalently, a graph is a cluster graph if and only if it has no three-vertex induced path; for this reason, the cluster graphs are also called **$P_{3}$-free graphs**. They are the [[complement graphs|0MCYJ72VGA]] of the complete multipartite graphs and the 2-leaf powers. The cluster graphs are [[transitively closed|05J9NWX07X]], and every transitively closed undirected graph is a cluster graph.