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
v3 · 2026-09-19 · History
Domain-specific #
1483
Domain group
Formal Sciences
Origin domain
Mathematics
Subdomain
Graph Theory → Mathematics
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.

How would you explain it like I'm…

Everyone-Is-Friends Group

Draw dots for kids and lines between kids who are friends. A clique is a group of kids where every single one is friends with every other one in the group. If even two of them are not friends, it is not a clique.

The All-Connected Group

A graph is a set of dots with lines connecting some pairs. A clique is a group of dots where every pair of dots in the group is connected by a line. For example, three dots all joined to each other make a triangle, which is a clique of size three. If even one pair in the group is missing its line, the group is not a clique.

Complete Vertex Subset

In an undirected graph G = (V, E), a clique is a subset C of the vertices such that every two distinct vertices in C are adjacent. Equivalently, the subgraph induced by C, meaning C together with all edges of G between its vertices, is a complete graph. What matters is the vertex set and pairwise adjacency: you check every pair inside the set. A clique need not be the largest possible; any fully connected subset qualifies, including a single vertex or a single edge.

 

Given an undirected graph G = (V, E), a clique is a vertex subset C ⊆ V in which every pair of distinct vertices is joined by an edge; equivalently, the induced subgraph G[C] is complete. The notion is defined on vertex subsets, relative to the adjacency of an undirected graph, and the test is pairwise adjacency, i.e. induced completeness. It is distinct from a complete graph as a standalone object (a clique is a subset inside some graph), from a maximal clique (one not contained in a larger clique), and from a maximum clique (one of largest size). Its complement notion is an independent set, a subset with no edges between its vertices.

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.

This entry is a kind of Network.

Network is the broader abstraction this entry instantiates. Relation, Completeness, Compatibility, Subset, Maximality, and Optimization are related.

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) — outgoing typed relations

  • Clique (Graph Theory) is a kind of Network Prime

    Network is the broader abstraction this entry instantiates.

Hierarchy path (1) — routes to 1 parentless root

  • Clique (Graph Theory) → is a kind of Network

Neighborhood in Abstraction Space

Clique (Graph Theory) sits in a sparse region of the domain-specific corpus (84th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Extremal Graph Theory & Bounds (7 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25

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 ↩