In the mathematical field of graph theory, the intersection number of a graph ${\displaystyle G=(V,E)}$ is the smallest number of elements needed to represent ${\displaystyle G}$ as an intersection graph of finite sets. 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 needed to cover all of the edges of ${\displaystyle G}$.

Intersection numbers have been studied under multiple names. A set of cliques that cover all edges of a graph is called a clique edge cover or edge clique cover, or even just a clique cover, although the last term is ambiguous: a clique cover can also be a set of cliques that cover all vertices of a graph. Sometimes "covering" is used in place of "cover". As well as being called the intersection number, the minimum number of these cliques has been called the R-content, edge clique cover number, or clique cover number. The problem of computing the intersection number has been called the intersection number problem, the intersection graph basis problem, covering by cliques, the edge clique cover problem, and the keyword conflict problem.

Every graph with ${\displaystyle n}$ vertices and ${\displaystyle m}$ edges has intersection number at most ${\displaystyle \min(m,n^{2}/4)}$. The intersection number is NP-hard to compute or approximate, but fixed-parameter tractable.

Let ${\displaystyle {\mathcal {F}}}$ be any family of sets, allowing sets in ${\displaystyle {\mathcal {F}}}$ to be repeated. Then the intersection graph of ${\displaystyle {\mathcal {F}}}$ is an undirected graph that has a vertex for each set in ${\displaystyle {\mathcal {F}}}$ and an edge between each two sets that have a nonempty intersection. Every graph can be represented as an intersection graph in this way. The intersection number of the graph is the smallest number ${\displaystyle k}$ such that there exists a representation of this type for which the union of the sets in ${\displaystyle {\mathcal {F}}}$ has ${\displaystyle k}$ elements. The problem of finding an intersection representation of a graph, using a given number of elements, is known as the intersection graph basis problem.

An alternative definition of the intersection number of a graph ${\displaystyle G}$ is that it is the smallest number of cliques in ${\displaystyle G}$ (complete subgraphs of ${\displaystyle G}$) that together cover all of the edges of ${\displaystyle G}$. A set of cliques with this property is known as a clique edge cover or edge clique cover, and for this reason the intersection number is also sometimes called the edge clique cover number.

The equality of the intersection number and the edge clique cover number has a short proof. In one direction, suppose that ${\displaystyle G}$ is the intersection graph of a family ${\displaystyle {\mathcal {F}}}$ of sets whose union ${\displaystyle U}$ has ${\displaystyle k}$ elements. Then for any element ${\displaystyle x\in U}$, the sets in ${\displaystyle {\mathcal {F}}}$ that contain ${\displaystyle x}$ form a clique ${\displaystyle K_{x}}$ in ${\displaystyle G}$, because each pair of these sets has a non-empty intersection containing ${\displaystyle x}$. Further, the cliques formed in this way cover every edge in ${\displaystyle G}$: if two sets in ${\displaystyle {\mathcal {F}}}$ form an edge by having a non-empty intersection, then that edge is contained in the clique ${\displaystyle K_{x}}$ for any element ${\displaystyle x}$ that belongs to their intersection. Therefore, the edges of ${\displaystyle G}$ can be covered by ${\displaystyle k}$ cliques, one per element of ${\displaystyle U}$.

In the other direction, if a graph ${\displaystyle G}$ can be covered by ${\displaystyle k}$ cliques, then each vertex ${\displaystyle v}$ of ${\displaystyle G}$ may be represented by a subset of the cliques, the ones that contain vertex ${\displaystyle v}$. Two of these subsets, for two vertices ${\displaystyle u}$ and ${\displaystyle v}$, have a nonempty intersection if and only if there is a clique in the intersection that contains both of them, if and only if there is an edge ${\displaystyle uv}$ included in one of the covering cliques.

The representation of a graph as an abstract intersection graph of sets can be used to construct more concrete geometric intersection representations of the same graph. In particular, if a graph has intersection number ${\displaystyle k}$, it can be represented as an intersection graph of ${\displaystyle k}$-dimensional unit hyperspheres. That is, its sphericity is at most ${\displaystyle k}$.