Skip to content

Clique (Graph Theory)

A vertex subset of an undirected graph in which every two distinct vertices are adjacent, equivalently an induced complete subgraph.

Version
v2 · 2026-09-06 · History
Domain-specific #
1483
Origin domain
mathematics
Subdomain
graph theory
Aliases
Graph clique, Complete vertex set, Complete subgraph vertex set

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

The recognition invariant is vertex subset + pairwise adjacency + undirected graph + induced completeness.

Structural Signature

  • An undirected graph, usually simple.
  • A selected vertex subset.
  • Every distinct vertex pair joined by an edge.
  • Induced subgraph isomorphic to a complete graph.
  • Size as the clique’s cardinality.
  • Maximality meaning inclusion-maximal.
  • Maximum meaning largest cardinality.
  • Clique number \(\omega(G)\).
  • Independent-set duality in the complement graph.
  • Triangle as a three-vertex clique.
  • Enumeration and decision variants.
  • Computational hardness for maximum/threshold problems.

What It Is Not

It is not necessarily maximal: a pair inside a triangle is a clique but can be enlarged. A maximal clique need not be maximum. It is not a connected component, community, or adolescent social clique unless the modeled relation is explicitly pairwise adjacency.[2]

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

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

  1. Fix graph type and adjacency semantics.
  2. Select candidate vertices.
  3. Check every distinct pair.
  4. To test maximality, search for any outside vertex adjacent to all members.
  5. To test maximum status, compare against all feasible cliques or a certified bound.
  6. Use complement duality where useful.
  7. 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.

Examples

Triangle. Its three vertices form a clique.

Maximal but not maximum. A small complete region can be unextendable while another larger clique exists elsewhere.

Non-example. Four vertices with five of six possible edges are dense but not a clique.

Structural Tensions

  • Local maximality versus global maximum.
  • Exact completeness versus noisy density.
  • Compact definition versus computational hardness.
  • Graph abstraction versus domain-specific edge meaning.
  • Enumeration output versus optimization certificate.

Structural–Framed Character

Pairwise compatibility, subset closure, and maximality are structural. Vertices, edges, induced subgraphs, complements, and clique algorithms are graph-theoretic frame.

Structural Core vs. Domain Accent

The portable core is universal pairwise satisfaction inside a subset. The constitutive accent is simple undirected adjacency and complete induced-subgraph semantics.

Network is the proposed immediate parent. Relation, Completeness, Compatibility, Subset, Maximality, and Optimization are related.

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

Relationships to Other Abstractions

Local relationship map for Clique (Graph Theory)Parents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.Clique (Graph Theory)DOMAINPrime abstraction: Network — is a kind ofNetworkPRIME

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

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

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

Not to Be Confused With

  • Adolescent Clique.
  • Complete connected component.
  • Dense community.
  • Maximal clique versus maximum clique.
  • Clique cover.
  • Clique graph derived from maximal cliques.

References

[1] Reinhard Diestel, Graph Theory, 5th ed., Springer, 2017. registry ↩

[2] J. A. Bondy and U. S. R. Murty, Graph Theory, Springer, 2008. registry ↩

[3] Richard M. Karp, “Reducibility Among Combinatorial Problems,” in Complexity of Computer Computations, Plenum, 1972. registry ↩

[4] J. W. Moon and L. Moser, “On Cliques in Graphs,” Israel Journal of Mathematics 3 (1965): 23–28. registry ↩