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.^[1] 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.

Recognition requires an analyst to fix the source graph and simple-graph convention, enumerate all and only maximal cliques, form one output vertex per maximal clique, add exactly the edges warranted by shared source vertices, and verify results up to graph isomorphism. Once established, it supports studying clique-graph recognition, iterated clique operators, Helly clique covers, graph classes, reconstruction questions, and structural relations among overlapping maximal complete subgraphs without turning those uses into the definition.

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.

Structural Signature¶

Carrier: a finite or otherwise suitably controlled simple undirected graph whose maximal cliques form a set-sized family
Inputs or antecedent state: the source graph, its complete vertex subsets, maximality under inclusion, the family of maximal cliques, nonempty set intersection, and graph-isomorphism convention
Constitutive operation: 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
Invariant: 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
Recognition test: fix the source graph and simple-graph convention, enumerate all and only maximal cliques, form one output vertex per maximal clique, add exactly the edges warranted by shared source vertices, and verify results up to graph isomorphism
Output or consequence: studying clique-graph recognition, iterated clique operators, Helly clique covers, graph classes, reconstruction questions, and structural relations among overlapping maximal complete subgraphs
Failure boundary: 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

What It Is Not¶

It is not the whole field of graph theory; many objects in that field do not satisfy its constitutive rule.
It is not its canonical example. 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. That is an instance, not a definition.
It is not Clique (Graph Theory). The accepted Clique entry is one complete vertex subset inside a graph; a clique graph is a new graph whose vertices represent all maximal cliques of a source graph and whose edges encode their intersections.
It is not an unrestricted metaphor. Some authors study variants using all cliques, maximum cliques, or edge-cliques, but the unqualified classical clique graph uses inclusion-maximal vertex cliques and nonempty vertex intersection

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.^[2]

Recognition. fix the source graph and simple-graph convention, enumerate all and only maximal cliques, form one output vertex per maximal clique, add exactly the edges warranted by shared source vertices, and verify results up to graph isomorphism
Comparison. Compare legitimate instances through finite or infinite carrier, maximal-clique convention, intersection threshold, source graph class, Helly property, iteration count, recognition complexity, and isomorphism convention.
Boundary. Some authors study variants using all cliques, maximum cliques, or edge-cliques, but the unqualified classical clique graph uses inclusion-maximal vertex cliques and nonempty vertex intersection
Use. Preserve every assumption when using the identity for studying clique-graph recognition, iterated clique operators, Helly clique covers, graph classes, reconstruction questions, and structural relations among overlapping maximal complete subgraphs.

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

Identity and measurement remain separate. Computing the output can require exponentially many maximal cliques, and recognition of clique graphs is computationally difficult; a visual guess is not a proof of preimage existence. Approximation or noisy evidence may weaken a classification without changing its definition.

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.
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.
Derive carefully. Infer studying clique-graph recognition, iterated clique operators, Helly clique covers, graph classes, reconstruction questions, and structural relations among overlapping maximal complete subgraphs only under the stated assumptions.
Stress-test. Contrast the legitimate boundary case—Some authors study variants using all cliques, maximum cliques, or edge-cliques, but the unqualified classical clique graph uses inclusion-maximal vertex cliques and nonempty vertex intersection—with this counterexample: the complete graph on one vertex for every clique of G is not K(G), because nonmaximal cliques must be omitted and disjoint maximal cliques must not be joined.

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.^[3]

Outside the domain, only the skeleton—replace a system's maximal cohesive substructures by nodes and connect those nodes when their memberships overlap—travels automatically. The terms clique, maximal clique, intersection graph, Helly family, edge cover, preimage, clique operator, graph isomorphism, and recognition retain domain-specific meanings, so every role and inference must be revalidated.

Examples¶

Canonical¶

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. Consecutive source edges share one endpoint and become adjacent, whereas the first and last edge are disjoint and remain nonadjacent. It is canonical because the carrier, rule, invariant, and consequence are all inspectable.^[1]

Mapped back: a finite or otherwise suitably controlled simple undirected graph whose maximal cliques form a set-sized family → 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 → 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 → studying clique-graph recognition, iterated clique operators, Helly clique covers, graph classes, reconstruction questions, and structural relations among overlapping maximal complete subgraphs

Applied / In Practice¶

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. The characterization concerns cliques in the candidate output and does not turn recognition into the simpler task of listing maximal cliques of a known preimage. It qualifies only after the same diagnostic and failure boundary are checked.^[2]

Mapped back: declared instance → recognition test → boundary check → qualified use

Structural Tensions¶

T1: Exact identity vs. practical recognition. The constitutive condition may be exact while evidence is indirect. Diagnostic: Can the reviewer state both the condition and the warrant?
T2: Canonical form vs. variants. classical clique graphs, iterated clique graphs, restricted source classes, Helly clique graphs, and explicitly qualified all-clique or edge-clique variants can preserve or change the identity. Diagnostic: Which named role is invariant across the variants?
T3: Compression vs. hidden assumptions. The label is useful only while prerequisites remain visible. Diagnostic: Can each downstream inference be traced to a declared assumption?
T4: Autonomy vs. reduction. The candidate uses broader structures but claims 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. Diagnostic: Does that residual still support independent recognition after the parent and neighbors are subtracted?

Structural–Framed Character¶

The entry is structurally mixed but domain-framed. Its portable skeleton is replace a system's maximal cohesive substructures by nodes and connect those nodes when their memberships overlap; its identity-bearing terms are clique, maximal clique, intersection graph, Helly family, edge cover, preimage, clique operator, graph isomorphism, and recognition. Those terms determine admissible objects, evidence, and consequences inside graph theory.

Structural Core vs. Domain Accent¶

The structural core is a carrier governed by 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 and tested by fix the source graph and simple-graph convention, enumerate all and only maximal cliques, form one output vertex per maximal clique, add exactly the edges warranted by shared source vertices, and verify results up to graph isomorphism. The domain accent is constitutive rather than decorative, so an analogy that preserves only the skeleton is not another instance of Clique graph.

This entry is a kind of Intersection.

Adjacency in the output graph is generated by intersection among the family of maximal clique sets, once the maximal cliques have been extracted and the graph rebuilt on them. What makes it its own entry is the maximal-clique intersection-graph operator together with the class of graphs in its image, which is neither a clique itself, nor a graph that merely contains many cliques, nor an arbitrary intersection graph.

Relationships to Other Abstractions¶

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

Clique graph → is a kind of Intersection → presupposes Set and Membership

Neighborhood in Abstraction Space¶

Clique graph sits in a crowded region of the domain-specific corpus (12^th 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

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-10-25

Not to Be Confused With¶

Clique. A complete vertex subset of one graph, serving as input data to the operator.
Clique complex. A simplicial complex containing every clique as a simplex, not an intersection graph of maximal cliques.
Line graph. Uses edges of the source graph as vertices and joins incident edges; it coincides only in special cases.
Clique number. A scalar maximum clique size rather than a graph transformation.

References¶

[1] Ronald C. Hamelink, 'A Partial Characterization of Clique Graphs,' Journal of Combinatorial Theory 5(2), 192–197 (1968), DOI 10.1016/S0021-9800(68)80055-9. registry ↩a ↩b

[2] Fred S. Roberts and Joel H. Spencer, 'A Characterization of Clique Graphs,' Journal of Combinatorial Theory, Series B 10(2), 102–108 (1971), DOI 10.1016/0095-8956(71)90070-0. registry ↩a ↩b

[3] Jayme L. Szwarcfiter and Claudson F. Bornstein, 'Clique Graphs of Chordal and Path Graphs,' SIAM Journal on Discrete Mathematics 7(2), 331–336 (1994), DOI 10.1137/S0895480191223191. registry ↩