# Clique graph

In graph theory, a **clique graph** of an undirected graph *G* is another graph *K*(*G*) that represents the structure of cliques in *G*.

Clique graphs were discussed at least as early as 1968, and a characterization of clique graphs was given in 1971.

## Formal definition

A clique of a graph *G* is a set *X* of vertices of *G* with the property that every pair of distinct vertices in *X* are adjacent in *G*.
A maximal clique of a graph *G* is a clique *X* of vertices of *G*, such that there is no clique *Y* of vertices of *G* that contains all of *X* and at least one other vertex.

Given a graph *G*, its clique graph *K*(*G*) is a graph such that

every vertex of *K*(*G*) represents a maximal clique of *G*; and
two vertices of *K*(*G*) are adjacent when the underlying cliques in *G* share at least one vertex in common.
The clique graph *K*(*G*) can also be characterized as the intersection graph of the maximal cliques of *G*.

## Characterization

A graph *H* is the clique graph *K*(*G*) of another graph if and only if there exists a collection *C* of cliques in *H* whose union covers all the edges of *H*, such that *C* forms a Helly family. This means that, if *S* is a subset of *C* with the property that every two members of *S* have a non-empty intersection, then *S* itself should also have a non-empty intersection. However, the cliques in *C* do not necessarily have to be maximal cliques.