Clique — Definition, Formula & Examples

A clique is a group of vertices in a graph where every vertex is joined by an edge to every other vertex in the group. Think of a circle of friends in which everyone knows everyone else.

Let $G = (V, E)$ be a simple undirected graph. A subset $S \subseteq V$ is a clique if for all distinct $u, v \in S$ , the edge $\{u, v\} \in E$ . Equivalently, the induced subgraph $G[S]$ is a complete graph $K_{|S|}$ . The clique number $\omega(G)$ is the size of the largest clique in $G$ . A clique is maximal if no other vertex can be added to it, and maximum if no clique in $G$ is larger.

Key Formula

\text{edges in a clique of size } k = \binom{k}{2} = \frac{k(k-1)}{2}

Where:

$k$ = number of vertices in the clique
$\binom{k}{2}$ = number of distinct pairs of vertices, each of which must be joined by an edge

How It Works

To test whether a set of

k

vertices is a clique, you check every pair of them. There are

\binom{k}{2}

pairs, and all of those edges must be present. To find the clique number, you search for the largest set that passes this test. Degrees give a quick filter: a vertex in a clique of size

k

must have degree at least

k - 1

, so you can rule out vertices with too few neighbors.

Worked Example

Problem: A graph has vertices A, B, C, D, E and edges AB, AC, AD, BC, BD, CD, DE. Find the clique number

\omega(G)

Step 1: List the degrees. A, B, and C each have 3 neighbors. D has 4 neighbors (A, B, C, E). E has 1 neighbor (D).

\deg(A)=\deg(B)=\deg(C)=3,\quad \deg(D)=4,\quad \deg(E)=1

Step 2: Rule out a clique of size 5. Every vertex in it would need degree at least

5 - 1 = 4

. Vertex E has degree 1, so no 5-vertex clique exists.

5 - 1 = 4 > \deg(E) = 1

Step 3: Test the set {A, B, C, D}. A clique on 4 vertices needs every pair joined. The edges AB, AC, AD, BC, BD, CD are all present, so the set is a clique.

\binom{4}{2} = \frac{4 \cdot 3}{2} = 6 \text{ edges required, 6 present}

Answer: The set {A, B, C, D} is a maximum clique, so

\omega(G) = 4

Why It Matters

Cliques are a core topic in discrete mathematics and algorithms courses. There they serve as a standard example of an NP-complete problem and give a lower bound for graph coloring, since

\chi(G) \ge \omega(G)

. Analysts also use clique detection to find tightly connected groups in social networks and protein-interaction networks.

Common Mistakes

Mistake: Treating a maximal clique as a maximum clique.

Correction: In the worked example, {D, E} is maximal because no other vertex is adjacent to both D and E. It has only 2 vertices, though, while the maximum clique has 4. Maximal means it cannot be extended. Maximum means it is the largest in the whole graph.

Mistake: Calling any closed loop of vertices a clique, such as a 4-cycle A–B–C–D–A.

Correction: A cycle connects only consecutive vertices. A clique needs every pair connected, including the diagonals AC and BD. A 4-vertex clique needs all 6 edges, but a 4-cycle has only 4.

Related Terms

Bipartite Graph — Has no triangles, so clique number at most 2
Acyclic Graph — Contains no cycles, so no clique exceeds 2 vertices
Cayley Graph — Group-based graphs whose cliques reflect group structure
Pseudograph — Allows loops and multi-edges; cliques usually assume simple graphs
Bar Graph — Statistical chart, a different meaning of graph