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.
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.
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¶
- 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¶
Current abstraction Clique graph Domain-specific
Parents (1) — more general patterns this builds on
-
Clique graph is a kind of Intersection Prime
The proposed strict upward parent is
prime:intersection.
Hierarchy path (1) — routes to 1 parentless root
- Clique graph → Intersection → Set and Membership
Neighborhood in Abstraction Space¶
Clique graph sits in a crowded region of the domain-specific corpus (21st percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.
Family — Unclustered & Miscellaneous (1565 abstractions)
Nearest neighbors
- Intersection number (graph theory) — 0.93
- Split graph — 0.92
- Intersection graph — 0.91
- Local complementation — 0.91
- Clique-sum — 0.91
Computed from structural-signature embeddings · 2026-09-08