Skip to content

Clique graph

Transform an undirected graph into the intersection graph of its maximal cliques, making each maximal clique a vertex and joining two when their underlying vertex sets intersect.

Version
v3 · 2026-09-19 · History
Domain-specific #
1482
Domain group
Formal Sciences
Origin domain
Mathematics
Subdomains
Graph Theory, Intersection Graph Operators → Mathematics

Core Idea

The clique graph (K(G)) of an undirected graph (G) has one vertex for every maximal clique of (G), with two distinct vertices adjacent exactly when their corresponding maximal cliques have nonempty intersection. The construction first extracts inclusion-maximal complete vertex sets and then applies the intersection-graph operation to that family, discarding the internal vertices except insofar as shared membership generates adjacency.

Its autonomous residual is the maximal-clique intersection-graph operator and the class of graphs in its image, not a clique itself, a graph containing many cliques, or an arbitrary intersection graph. The identity fails when nonmaximal cliques are included without a variant declaration, adjacency is based on edge overlap rather than vertex overlap, the output is confused with the clique complex, or K(G) is treated as a numerical clique invariant.

How would you explain it like I'm…

The Friend-Group Map

Draw dots for kids and lines between kids who are friends. Find every biggest group where everyone is friends with everyone else, so no one else could join. Make a new dot for each of those groups, and connect two new dots if their groups share at least one kid. That new picture is the clique graph.

The Overlapping Groups Graph

A graph is dots connected by lines. A clique is a group of dots that are all connected to each other, and a maximal clique is one that cannot get any bigger by adding another dot. To make the clique graph of a graph, first find every maximal clique. Then draw a brand-new graph with one dot for each maximal clique, and connect two of those new dots if their cliques share at least one original dot. The original dots themselves do not appear in the new graph; they only decide which cliques get connected.

Maximal Clique Intersection Graph

Given an undirected graph G, its clique graph K(G) has one vertex for each maximal clique of G (a set of pairwise adjacent vertices that is not contained in any larger such set). Two vertices of K(G) are adjacent exactly when their maximal cliques share at least one vertex. So K(G) is the intersection graph of the family of maximal cliques. Details matter: using all cliques instead of only maximal ones gives a different construction, and overlap is judged by shared vertices, not shared edges. K(G) is a new graph, not a number like the clique number, and not the clique complex. Studying which graphs are clique graphs, or applying K repeatedly, are research questions that come after the definition.

 

For an undirected simple graph G, the clique graph K(G) has vertex set equal to the set of maximal cliques of G, with two distinct maximal cliques adjacent iff they have nonempty (vertex) intersection. Constructing it means enumerating all and only the inclusion-maximal complete vertex sets, then applying the intersection-graph operation to that family; the original vertices survive only through the shared memberships that generate edges. The object is an operator on graphs, together with the class of graphs in its image. It must not be confused with a clique itself, with graphs merely containing many cliques, with arbitrary intersection graphs, with the clique complex, or with any numerical clique invariant. Variants that include non-maximal cliques or use edge overlap for adjacency are different constructions and must be declared. Outputs are compared up to isomorphism. The operator supports questions such as clique-graph recognition, iterated clique operators K(K(G)), Helly clique covers, graph classes, and reconstruction.

Scope of Application

Clique graph applies when the analyst can specify a finite or otherwise suitably controlled simple undirected graph whose maximal cliques form a set-sized family and establish that vertices of the output correspond bijectively to maximal cliques of the input and output adjacency is equivalent to nonempty intersection of the corresponding vertex sets. The entry concerns the classical undirected simple-graph operator. Directed, hypergraph, weighted-overlap, and thresholded variants require separate definitions.

Clarity

A clear claim names the carrier, governing rule, assumptions, and recognition test. This matters because clique graph can be misread as any graph rich in cliques or as the accepted Clique object; the operator notation and maximal-clique carrier must be explicit. The disciplined statement is that the object counts as Clique graph exactly when vertices of the output correspond bijectively to maximal cliques of the input and output adjacency is equivalent to nonempty intersection of the corresponding vertex sets

Manages Complexity

The abstraction compresses classical clique graphs, iterated clique graphs, restricted source classes, Helly clique graphs, and explicitly qualified all-clique or edge-clique variants into a stable carrier, rule, invariant, and failure boundary. It makes comparison tractable while retaining the variables that control validity.

Compression can hide assumptions. A responsible use therefore declares finite or infinite carrier, maximal-clique convention, intersection threshold, source graph class, Helly property, iteration count, recognition complexity, and isomorphism convention and returns to the full diagnostic whenever a convention or boundary case changes.

Abstract Reasoning

  1. Type the carrier. Establish a finite or otherwise suitably controlled simple undirected graph whose maximal cliques form a set-sized family and reject examples from a different problem.
  2. Lock the rule. Express that vertices of the output correspond bijectively to maximal cliques of the input and output adjacency is equivalent to nonempty intersection of the corresponding vertex sets independently of one notation or implementation.

Knowledge Transfer

Transfer within graph theory is strong when new cases preserve the same carrier, mechanism, and diagnostic. The move from If the source graph is a path on four vertices, its three edges are the maximal cliques, so its clique graph is again a path on three vertices. to A graph can be tested for membership in the image of the clique-graph operator through the existence of an edge-covering Helly family of cliques. demonstrates that continuity.

Relationships to Other Abstractions

Local relationship map for Clique graphParents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.Clique graphDOMAINPrime abstraction: Intersection — is a kind ofIntersectionPRIME

Current abstraction Clique graph Domain-specific

Parents (1) — outgoing typed relations

  • Clique graph is a kind of Intersection Prime

    Output adjacency is literally generated by intersection among the family of maximal clique sets; maximal-clique extraction and graph reconstruction provide the domain-specific residual.

Hierarchy path (1) — routes to 1 parentless root

Neighborhood in Abstraction Space

Clique graph sits in a crowded region of the domain-specific corpus (12th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Graph Classes & Invariants (40 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25