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.

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.

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

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.

Relationships to Other Abstractions

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 (84^th 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

• Connected Dominating Set — 0.84
• Simplex Graph — 0.83
• Well-covered graph — 0.83
• Clique graph — 0.82
• Homogeneous Graph — 0.80

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