Clique (Graph Theory)¶
A vertex subset of an undirected graph in which every two distinct vertices are adjacent, equivalently an induced complete subgraph.
Core Idea¶
In an undirected graph \(G=(V,E)\), a clique is a subset \(C\subseteq V\) such that every two distinct vertices in \(C\) are adjacent. Equivalently, the subgraph induced by \(C\) is complete.
The recognition invariant is vertex subset + pairwise adjacency + undirected graph + induced completeness.
Scope of Application¶
Cliques encode mutually compatible choices, pairwise-conflicting constraints, dense graph motifs, social acquaintance groups, molecular interactions, bioinformatics matches, and reductions between graph problems. The decision problem asking whether a clique of size at least \(k\) exists is NP-complete.
Clarity¶
Pairwise adjacency is exact. High internal density below completeness is not a clique. In directed, weighted, temporal, or uncertain networks, the adjacency relation must first be converted into an explicit undirected criterion.
Manages Complexity¶
The clique predicate compresses \(\binom{|C|}{2}\) adjacency requirements into one named object. Complement duality converts clique questions into independent-set questions, and maximal-clique algorithms bound search through local extension rules.
Abstract Reasoning¶
- Fix graph type and adjacency semantics.
- Select candidate vertices.
- Check every distinct pair.
- To test maximality, search for any outside vertex adjacent to all members.
- To test maximum status, compare against all feasible cliques or a certified bound.
- Use complement duality where useful.
- Separate enumeration, decision, and optimization claims.
Knowledge Transfer¶
The portable structure is a subset whose members satisfy a relation pairwise without exception. The proposed immediate parent is Network.
Relationships to Other Abstractions¶
Current abstraction Clique (Graph Theory) Domain-specific
Parents (1) — more general patterns this builds on
-
Clique (Graph Theory) is a kind of Network Prime
Network is the proposed immediate parent.
Hierarchy path (1) — routes to 1 parentless root
- Clique (Graph Theory) → Network → Reservoir-Flux Network → Conservation Laws → Invariance
Neighborhood in Abstraction Space¶
Clique (Graph Theory) sits in a sparse region of the domain-specific corpus (87th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Graph Density, Distance & Planarity (11 abstractions)
Nearest neighbors
- Simplex Graph — 0.83
- Clique graph — 0.82
- Homogeneous Graph — 0.80
- Degree diameter problem — 0.79
- Turán Graph — 0.78
Computed from structural-signature embeddings · 2026-09-08