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: v2 · 2026-08-30 · History
Domain-specific #: 1482
Origin domain: graph theory
Subdomain: intersection graph operators

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.

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.

The proposed strict upward parent is prime:intersection. 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. The edge is proposal-only and points to a frozen prior-baseline Prime.

The entry does not collapse into the parent because 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 A thematic neighbor is declined whenever it does not literally subsume that rule.

The prospective workspace queue contains one strict upward edge to prime:intersection. No live DAG mutation is authorized.

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 (21^st 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

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 ↩