 Clique (graph theory)

A clique in a simple graph $G$ is a set $C$ of vertices such that every pair of distinct members is adjacent. Equivalently, its induced subgraph $G[C]$ is a complete graph. The surrounding graph need not itself be complete: a clique describes complete pairwise connectivity within a selected group.

Consider the original graph withThe set $\{a,b,c\}$ is a clique because all three pairs $ab,ac,bc$ are edges. The set $\{b,c,d\}$ is not a clique: the edge $bd$ is missing. A path in a graph connecting all selected vertices is therefore insufficient; every pair must have a direct edge.

Here the clique number is $3$. The maximum clique is $\{a,b,c\}$, but $\{c,d\}$ and $\{d,e\}$ are also maximal cliques. This distinction is useful when an algorithm stops as soon as its current clique cannot be enlarged: that stopping condition establishes maximality, while finding the largest possible clique is a separate requirement.

In graph theory, a **clique** is a subset of vertices in an undirected graph such that every two distinct vertices in the clique are adjacent. In simpler terms, a clique is a complete subgraph where every vertex is connected to every other vertex. More formally, a clique of size \( k \) is a set of \( k \) vertices such that there are edges between every pair of vertices in that set.