Clique-sum¶

Combine graphs by choosing equally sized complete subgraphs, identifying their vertices through a bijection, and optionally deleting interface-clique edges under an explicit convention.

Version: v1 · 2026-08-30 · History
Domain-specific #: 1484
Origin domain: graph theory
Subdomain: graph decomposition and minors

Core Idea¶

A clique-sum is a graph-composition operation that takes the disjoint union of two graphs and identifies corresponding vertices of selected equal-order cliques, with interface-edge deletion governed by the chosen convention.^[1] Disjoint summands preserve their off-interface vertices and edges, quotient identification fuses matched clique vertices, and the edge convention determines which clique edges survive in the resulting graph The abstraction is therefore identified by a declared carrier, a transformation or constraint over that carrier, and an invariant that tells an analyst whether the named structure is genuinely present.

The load-bearing residual is not the broad topic of graph theory. It is the clique-qualified gluing operation and its convention-sensitive interface, distinct from merely finding a clique, taking a union, or asserting a separator decomposition. That residual remains recognizable when examples, notation, scale, or implementation change, but it disappears if the chosen interface is not complete, vertices are connected without identification, the summands overlap outside the interface, or edge deletion changes off-interface structure. This gives the entry an operational identity rather than merely a historical label.

A useful analysis keeps three layers separate. The constitutive layer says what must be true: the overlap is exactly the image of two complete subgraphs matched by a declared bijection, and all changes outside that interface are excluded. The evidential layer asks what observation or proof warrants the claim: verify each interface is a clique of the stated order, record whether order means exactly or at most \(k\), state the vertex bijection and edge-deletion convention, and reconstruct each summand away from the shared interface. The use layer asks what reasoning becomes available once the identity is established: expressing graphs as pieces joined through bounded separators, proving closure of graph classes, relating treewidth to decompositions, and formulating graph-minor structure theorems. Conflating the layers is the most common source of scope inflation.

Structural Signature¶

Carrier: two finite graphs, a clique in each, and a bijection between the selected clique vertices
Inputs or antecedent state: summand graphs, interface cliques of equal size, an identification bijection, a convention for deleting none, some, or all interface edges, and optional repeated composition
Constitutive operation: Disjoint summands preserve their off-interface vertices and edges, quotient identification fuses matched clique vertices, and the edge convention determines which clique edges survive in the resulting graph
Invariant: the overlap is exactly the image of two complete subgraphs matched by a declared bijection, and all changes outside that interface are excluded
Recognition test: verify each interface is a clique of the stated order, record whether order means exactly or at most \(k\), state the vertex bijection and edge-deletion convention, and reconstruct each summand away from the shared interface
Output or consequence: expressing graphs as pieces joined through bounded separators, proving closure of graph classes, relating treewidth to decompositions, and formulating graph-minor structure theorems
Failure boundary: the chosen interface is not complete, vertices are connected without identification, the summands overlap outside the interface, or edge deletion changes off-interface structure

What It Is Not¶

It is not the whole field of graph theory. The field contains many questions and methods that do not instantiate Clique-sum.
It is not its most familiar example. A 1-clique-sum identifies one vertex from each of two graphs, producing a graph with a cut vertex joining the pieces. exhibits the structure, but the example is evidence for the abstraction rather than its definition.
It is not the neighboring catalog concept Clique (Graph Theory). A clique is a complete subgraph used as the interface; a clique-sum is an operation on whole graphs that identifies two such interfaces.
It is not a claim that every boundary case has one uncontested classification. Graph-minor, chordal-graph, and SPQR contexts use different interface-edge deletion conventions, so the same summands and vertex matching can produce different results
It is not an unrestricted metaphor for any process that seems similar. Outside graph theory, the vocabulary and validity conditions do not transfer literally.

Scope of Application¶

Clique-sum belongs to graph theory and is useful where the analyst can specify two finite graphs, a clique in each, and a bijection between the selected clique vertices, then evaluate the overlap is exactly the image of two complete subgraphs matched by a declared bijection, and all changes outside that interface are excluded. The scope is broad within that domain but bounded by the need for the overlap is exactly the image of two complete subgraphs matched by a declared bijection, and all changes outside that interface are excluded. The entry treats finite undirected graph conventions; matroid sums and topological connected sums are related analogies but require their own definitions.^[2]

Definition and recognition. Determine whether a proposed instance satisfies the constitutive conditions rather than merely sharing terminology.
Construction or evolution. Track how summand graphs, interface cliques of equal size, an identification bijection, a convention for deleting none, some, or all interface edges, and optional repeated composition are converted, constrained, or organized by Disjoint summands preserve their off-interface vertices and edges, quotient identification fuses matched clique vertices, and the edge convention determines which clique edges survive in the resulting graph.
Comparison. Compare instances using interface order, exactly versus at-most convention, bijection, retained interface edges, simple or multigraph carrier, associativity up to isomorphism, treewidth, and separator behavior, without treating convenience measures as the definition.
Boundary analysis. Diagnose cases where Graph-minor, chordal-graph, and SPQR contexts use different interface-edge deletion conventions, so the same summands and vertex matching can produce different results and state which convention or theorem controls the decision.
Downstream reasoning. Use the established identity to support expressing graphs as pieces joined through bounded separators, proving closure of graph classes, relating treewidth to decompositions, and formulating graph-minor structure theorems while preserving the assumptions under which the inference is valid.

Clarity¶

The abstraction clarifies a crowded vocabulary by making the overlap is exactly the image of two complete subgraphs matched by a declared bijection, and all changes outside that interface are excluded the center of the account. A claim should name the carrier, the governing operation or relation, the applicable assumptions, and the recognition test. A bare label is insufficient because some sources reserve k-sum for exact order and others for order at most k, while edge-deletion rules range from none to all. The disciplined statement is: given summand graphs, interface cliques of equal size, an identification bijection, a convention for deleting none, some, or all interface edges, and optional repeated composition, the structure counts as Clique-sum exactly when the overlap is exactly the image of two complete subgraphs matched by a declared bijection, and all changes outside that interface are excluded.

This format also separates identity from measurement. Correctness is checked combinatorially from interfaces and resulting adjacency, not by visual resemblance of a drawing. Measurements can be noisy, implementations can approximate, and proofs can use equivalent characterizations; none of those facts licenses changing the object being measured. When reports disagree, first check scope and convention, then data or proof, and only then interpret the disagreement as substantive.

Manages Complexity¶

Without the abstraction, an analyst must reason directly over many local details: the carrier roles, admissibility assumptions, competing conventions, derived invariants, boundary cases, and proof or validation obligations specific to Clique-sum. Clique-sum compresses them into the roles in the structural signature. That compression permits comparison across instances without erasing the variables that determine validity. It also exposes which details may be varied safely and which are constitutive.

The compression has a price. A single label can hide zero-, one-, two-, and three-clique sums, repeated tree-like gluing, full or partial interface-edge deletion, simple-graph cleanup, and theorem-specific notation. Good use therefore carries a small declaration of assumptions alongside the name. The abstraction manages complexity when it reduces the state space of the question while keeping the failure boundary visible; it mismanages complexity when the label substitutes for that boundary analysis.

Abstract Reasoning¶

Identify the carrier. State what the elements, states, objects, or observations are: two finite graphs, a clique in each, and a bijection between the selected clique vertices. Reject examples whose alleged carrier belongs to a different problem.
Lock the constitutive rule. Express the overlap is exactly the image of two complete subgraphs matched by a declared bijection, and all changes outside that interface are excluded independently of one notation or implementation. This step prevents the canonical example from becoming the definition.
Derive consequences. From the overlap is exactly the image of two complete subgraphs matched by a declared bijection, and all changes outside that interface are excluded, infer expressing graphs as pieces joined through bounded separators, proving closure of graph classes, relating treewidth to decompositions, and formulating graph-minor structure theorems. Record each assumption used so that a later change of setting does not silently preserve an invalid conclusion.
Test adversarial cases. Examine Graph-minor, chordal-graph, and SPQR contexts use different interface-edge deletion conventions, so the same summands and vertex matching can produce different results and adding all edges between two selected cliques without identifying their vertices is a join-like construction, not a clique-sum. A robust identity explains why the first is convention-sensitive and why the second is outside the class.
Compare and refine. Use interface order, exactly versus at-most convention, bijection, retained interface edges, simple or multigraph carrier, associativity up to isomorphism, treewidth, and separator behavior to compare legitimate instances, and refine the model when discrepancies reflect hidden variation rather than failure of the abstraction itself.

Knowledge Transfer¶

Knowledge transfers strongly among subfields of graph theory because they reuse two finite graphs, a clique in each, and a bijection between the selected clique vertices, Disjoint summands preserve their off-interface vertices and edges, quotient identification fuses matched clique vertices, and the edge convention determines which clique edges survive in the resulting graph, and verify each interface is a clique of the stated order, record whether order means exactly or at most \(k\), state the vertex bijection and edge-deletion convention, and reconstruct each summand away from the shared interface. A theorem, diagnostic, or modeling warning can travel when those roles remain literal. For example, the distinction between constitutive identity and a convenient observable transfers from A 1-clique-sum identifies one vertex from each of two graphs, producing a graph with a cut vertex joining the pieces. to Repeated 2-clique-sums of suitable pieces describe series–parallel and bounded-treewidth constructions under standard conventions..^[3]

Transfer outside the home domain is weaker. The skeletal pattern—combine structured objects by identifying isomorphic boundary interfaces while preserving each object's off-boundary structure—may suggest an analogy, but the domain-specific mechanisms, admissible evidence, and consequences do not come along automatically. The safe transfer procedure maps each role explicitly, checks the invariant again, and refuses the name when only a superficial resemblance remains.

Examples¶

Canonical¶

A 1-clique-sum identifies one vertex from each of two graphs, producing a graph with a cut vertex joining the pieces. Each one-vertex interface is automatically a clique, there are no clique edges to delete, and removing the identified vertex separates the surviving off-interface pieces. This example is canonical because every role can be inspected: the carrier is two finite graphs, a clique in each, and a bijection between the selected clique vertices; the operative rule is Disjoint summands preserve their off-interface vertices and edges, quotient identification fuses matched clique vertices, and the edge convention determines which clique edges survive in the resulting graph; the invariant is the overlap is exactly the image of two complete subgraphs matched by a declared bijection, and all changes outside that interface are excluded; and the result supports expressing graphs as pieces joined through bounded separators, proving closure of graph classes, relating treewidth to decompositions, and formulating graph-minor structure theorems.^[1] Changing incidental notation or scale leaves the structure intact, while removing the overlap is exactly the image of two complete subgraphs matched by a declared bijection, and all changes outside that interface are excluded destroys the classification.

Mapped back: two finite graphs, a clique in each, and a bijection between the selected clique vertices → Disjoint summands preserve their off-interface vertices and edges, quotient identification fuses matched clique vertices, and the edge convention determines which clique edges survive in the resulting graph → the overlap is exactly the image of two complete subgraphs matched by a declared bijection, and all changes outside that interface are excluded → expressing graphs as pieces joined through bounded separators, proving closure of graph classes, relating treewidth to decompositions, and formulating graph-minor structure theorems

Applied / In Practice¶

Repeated 2-clique-sums of suitable pieces describe series–parallel and bounded-treewidth constructions under standard conventions. The decomposition claim depends on whether the interface has exactly or at most two vertices and on which edge-retention convention the theorem uses. The applied case is not licensed merely by vocabulary. It qualifies because the same recognition test—verify each interface is a clique of the stated order, record whether order means exactly or at most \(k\), state the vertex bijection and edge-deletion convention, and reconstruct each summand away from the shared interface—can be run and because the same failure boundary—the chosen interface is not complete, vertices are connected without identification, the summands overlap outside the interface, or edge deletion changes off-interface structure—remains meaningful.^[2] The case also shows why practical outputs should report assumptions, resolution, and uncertainty instead of a naked label.

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

Structural Tensions¶

T1: Axiomatic identity vs. operational recognition. The defining conditions may be exact while empirical or computational recognition is approximate. Neither pole can be removed without changing the analytical task. Diagnostic: Can the reviewer state both the exact condition and the evidence used to infer it?
T2: Local roles vs. global consequence. The mechanism is enacted through local relations, but the abstraction is usually valued for a global classification or prediction. Neither pole can be removed without changing the analytical task. Diagnostic: Does the claimed global result actually follow from the declared local conditions?
T3: Ideal form vs. finite representation. Theory states a clean invariant while data structures, measurements, or proofs expose only finite representations. Neither pole can be removed without changing the analytical task. Diagnostic: Would increasing resolution converge toward the same classification?
T4: Canonical convention vs. legitimate variants. A standard formulation supports communication, while variants may preserve the same core under changed assumptions. Neither pole can be removed without changing the analytical task. Diagnostic: Which role is invariant across variants, and which convention-specific conclusion changes?
T5: Compression vs. hidden assumptions. The name compresses a complex argument but can conceal prerequisites. Neither pole can be removed without changing the analytical task. Diagnostic: Can each downstream inference be traced to an explicit assumption?
T6: Autonomous residual vs. reduction to catalog neighbors. The candidate uses broader structures but adds an identity-bearing residual. Neither pole can be removed without changing the analytical task. Diagnostic: After subtracting the proposed parent and named neighbors, does the constitutive residual still support independent diagnostics?

Structural–Framed Character¶

The entry is structurally mixed but domain-framed. Its portable skeleton is combine structured objects by identifying isomorphic boundary interfaces while preserving each object's off-boundary structure. Its identity-bearing terms—clique, separator, disjoint union, vertex identification, quotient graph, graph minor, treewidth, and decomposition—derive their meaning from graph theory and cannot be replaced by generic systems language without losing the tests that distinguish valid from invalid instances.

This mixed character explains why the abstraction is reusable inside the domain yet does not meet the Prime bar. The structure organizes reasoning, but its claims still depend on domain-specific objects, evidence, and intervention semantics.

Structural Core vs. Domain Accent¶

The structural core consists of a carrier, Disjoint summands preserve their off-interface vertices and edges, quotient identification fuses matched clique vertices, and the edge convention determines which clique edges survive in the resulting graph, a recognition invariant, and a consequence. That skeleton may resemble patterns elsewhere, especially combine structured objects by identifying isomorphic boundary interfaces while preserving each object's off-boundary structure. The domain accent is not decorative: clique, separator, disjoint union, vertex identification, quotient graph, graph minor, treewidth, and decomposition determine what counts as an admissible carrier, a valid transition, and successful evidence.

The abstraction therefore remains domain-specific. A cross-domain reuse that preserves only words such as 'balance,' 'cut,' 'sequence,' 'loss,' or 'simulation' is metaphor. Literal transfer requires the original role structure and diagnostics, which in this case remain anchored in graph theory.

The proposed strict upward parent is prime:transformation. Clique-sum is literally a rule-governed mapping from graphs plus interface data to a new graph, preserving off-interface structure while altering identification and selected interface edges. This is a proposal-only workspace relationship: the accepted Prime supplies a genuinely instantiated structural prerequisite or superclass, while Clique-sum adds domain-specific constraints.

The entry does not collapse into that parent because the clique-qualified gluing operation and its convention-sensitive interface, distinct from merely finding a clique, taking a union, or asserting a separator decomposition It also declines a nearby thematic catalog node: the neighbor does not literally subsume the constitutive identity of Clique-sum. This explicit assert-and-decline pattern keeps the proposed DAG narrow and prevents a merely thematic edge.

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

Relationships to Other Abstractions¶

Current abstraction Clique-sum Domain-specific

Parents (1) — more general patterns this builds on

Clique-sum is a kind of Transformation Prime

The proposed strict upward parent is prime:transformation.

Hierarchy path (1) — routes to 1 parentless root

Clique-sum → Transformation → Function (Mapping)

Neighborhood in Abstraction Space¶

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

Split graph — 0.91
Biclique-free graph — 0.91
Intersection number (graph theory) — 0.91
Clique graph — 0.91
Join (graph theory) — 0.91

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With¶

Clique. The complete interface subgraph, not the gluing operation.
Graph union. Combines vertex and edge sets without necessarily identifying matched clique vertices.
Graph join. Adds all cross-edges between two disjoint vertex sets.
Connected sum. A topological analogue with different carriers and equivalence conditions.

References¶

[1] Reinhard Diestel, Graph Theory, 5^th ed., Springer, 2017, sections on tree-decompositions and graph minors, DOI 10.1007/978-3-662-53622-3. registry ↩a ↩b

[2] Neil Robertson and Paul D. Seymour, 'Graph Minors. XVI. Excluding a Non-planar Graph,' Journal of Combinatorial Theory, Series B 89(1), 43–76 (2003), DOI 10.1016/S0095-8956(03)00042-X. registry ↩a ↩b

[3] Erik D. Demaine and MohammadTaghi Hajiaghayi, 'Linearity of Grid Minors in Treewidth with Applications through Bidimensionality,' Combinatorica 28, 19–36 (2008), DOI 10.1007/s00493-008-2140-4. registry ↩