Cliques and Independent Sets — Mathematics Knowledge System

Overview

A clique in a graph is a set of vertices that are all pairwise adjacent — a fully-connected 'mini complete graph' sitting inside the larger one. An independent set is the opposite extreme: a set of vertices with no edges between any of them at all. The two notions are mirror images of each other through graph complementation: a clique in G is exactly an independent set in G's complement Ḡ (the graph with the same vertices but edges swapped for non-edges), so every clique-finding fact has an independent-set twin. Both are central to combinatorics: finding the largest clique (clique number ω(G)) or largest independent set (independence number α(G)) are both NP-hard in general, and Ramsey theory asks a deeper question — how large must a graph be before it's forced to contain a clique or independent set of a given size, no matter how its edges are arranged.

Intuition

Think of vertices as people at a party and edges as 'know each other'. A clique is a group where everyone already knows everyone else — perfect for introducing them as a unit, no awkward strangers. An independent set is the opposite: a group of total strangers, nobody knows anybody else in the group. Ramsey's theorem is the surprising guarantee that at ANY large enough party, you can always find one of these two extremes — either a clique of mutual friends or an independent set of total strangers of a given size — no matter how the friendships happen to be arranged. That's why R(3,3) = 6: any party of 6 people either has 3 mutual friends or 3 mutual strangers, guaranteed.

Formal Definition

Definition

For a graph G = (V, E), a clique is a subset S ⊆ V such that every two distinct vertices in S are adjacent; an independent set is a subset I ⊆ V such that no two vertices in I are adjacent. The clique number and independence number are the sizes of the largest such sets:

S \subseteq V \text{ is a clique} \iff \forall u,v \in S,\ u \ne v \implies \{u,v\} \in E

Clique

I \subseteq V \text{ is independent} \iff \forall u,v \in I,\ \{u,v\} \notin E

Independent set

\omega(G) = \alpha(\overline{G}), \qquad \alpha(G) = \omega(\overline{G})

Clique/independent-set duality via the complement graph

Worked Examples

A clique on k vertices has all C(k,2) possible edges present.
$\binom{3}{2} = 3$
3 vertices, all 3 possible edges present — this is exactly the complete graph K3, i.e. a triangle.
$K_3 = \text{triangle}$

Answer: 3 edges; a size-3 clique is exactly a triangle (K3).

Practice Problems

Difficulty 3/10

A clique has 6 vertices, all pairwise connected. How many edges does it contain?

Difficulty 4/10

In the 5-cycle C5 (vertices 1-2-3-4-5-1, only consecutive vertices adjacent), what is the size of the largest independent set?

Difficulty 6/10

A social media platform wants to find a group of 4 users who are all mutual friends (to suggest as a 'group chat'). In graph terms, what are they searching for, and why is this computationally hard at scale?

Quiz

Summary

A clique is a fully-connected subset of vertices (all C(k,2) edges present); an independent set has no edges between any of its vertices.
Cliques and independent sets are dual under graph complementation: ω(G) = α(Ḡ) and α(G) = ω(Ḡ).
Finding the maximum clique or maximum independent set is NP-hard in general graphs.
Ramsey's theorem guarantees that large enough graphs must contain a clique or independent set of a given size; R(3,3) = 6 is the classic small example.

References

WebsiteWikipedia — Clique (graph theory)
WebsiteWikipedia — Independent set (graph theory)
WebsiteWikipedia — Ramsey's theorem