---
tag: 8AKETP2GXQ
kind: concept
name: Intersection number (graph theory)
aliases: [clique-edge-cover, intersection-graph-basis]
sources:
  - wikipedia: en:31087478@r1371039908
    locator: Intersection number (graph theory)
    note: adopted
    mention: wikipedia://en/31087478
    sections: [Summary]
same_as:
  wikidata: Q17101799
  wikipedia: Intersection number (graph theory)
inventory: [W2G59K9D5H]
---

## Summary

In the mathematical field of graph theory, the **intersection number** of a graph $G=(V,E)$ is the smallest number of elements needed to represent $G$ as an intersection graph of [[finite sets|070R982G4B]]. In such a representation, each vertex is represented as a set, and two vertices are connected by an edge whenever their sets have a common element. The intersection number equals the smallest number of [[cliques|0BYX1D7C2E]] (subgraphs with edges between all pairs of vertices) needed to cover all of the edges of $G$. Both this number and the computational problem of finding it have been studied under many alternative names.