Chapter 64. Cliques

A clique is a set of vertices that are all adjacent to one another. Cliques represent complete mutual compatibility, complete interaction, or complete connectivity. They are among the most important structures in graph theory and appear throughout combinatorics, optimization, computer science, social networks, biology, and statistics. (en.wikipedia.org)

If independent sets describe sparse structure, then cliques describe dense structure. Much of graph theory studies the tension between these two extremes.

Clique problems are central in extremal graph theory and computational complexity.

64.1 Definition

Let

G=(V,E)

be a graph.

A subset

C \subseteq V

is called a clique if every pair of distinct vertices in $C$ is adjacent.

Equivalently,

\forall u,v \in C, \quad u \ne v \implies uv \in E.

Thus the subgraph induced by $C$ is complete.

For example, in the graph:

\{a,b,c,d\},

if the edges

ab,\; ac,\; bc

exist, then:

\{a,b,c\}

forms a clique.

64.2 Clique Number

A clique is maximum if it has largest possible size.

The size of a maximum clique is called the clique number and is denoted by:

\omega(G).

Thus:

\omega(G) = \max\{|C| : C \text{ is a clique in } G\}.

The maximum clique problem asks for a clique of largest possible size.

This problem is one of the classical NP-complete problems.

64.3 Maximal and Maximum Cliques

The terms maximal and maximum have different meanings.

Term	Meaning
Maximal clique	Cannot be enlarged
Maximum clique	Largest possible clique

Every maximum clique is maximal.

The converse is false.

Example

Suppose a graph contains:

Clique	Size
$\{a,b,c,d\}$	$4$
$\{x,y,z\}$	$3$

The second clique may still be maximal if no additional vertex can be added.

64.4 Cliques in Standard Graphs

Complete Graphs

For the complete graph:

K_n,

every subset of vertices forms a clique.

Thus:

\omega(K_n)=n.

Empty Graphs

If a graph contains no edges, then:

\omega(G)=1.

No two vertices are adjacent.

Paths

For the path graph $P_n$ ,

\omega(P_n)=2

when

n \ge 2.

Every edge forms a clique of size $2$ , but no larger clique exists.

Cycles

For cycle graphs:

Graph	Clique Number
$C_3$	$3$
$C_n,\; n\ge4$	$2$

Longer cycles contain no triangles.

Complete Bipartite Graphs

For

K_{m,n},

\omega(K_{m,n})=2.

Vertices inside the same part are never adjacent.

64.5 Cliques and Independent Sets

Cliques and independent sets are dual under graph complementation.

Let

\overline{G}

be the complement graph.

Then:

C \text{ is a clique in } G

if and only if

C \text{ is independent in } \overline{G}.

Therefore:

\omega(G)=\alpha(\overline{G}).

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

This duality is fundamental.

Many clique results can be translated into independent-set results and vice versa.

64.6 Cliques and Coloring

Graph coloring partitions vertices into independent sets.

Since every pair of vertices in a clique must receive different colors:

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

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

Thus the clique number provides a lower bound for the chromatic number.

Example

Since:

\omega(K_n)=n,

the complete graph requires $n$ colors.

In many graphs, however:

$$ \chi(G)

\omega(G). $$

Perfect graphs are precisely the graphs where equality always holds for every induced subgraph.

64.7 Triangle-Free Graphs

A graph is triangle-free if it contains no clique of size $3$ .

Equivalently:

\omega(G)\le2.

Triangle-free graphs may still contain many edges.

For example, complete bipartite graphs are triangle-free regardless of size.

Triangle-free graphs play an important role in extremal graph theory.

64.8 Clique Detection

Determining whether a graph contains a clique of size $k$ is called the clique decision problem.

Input:

Object	Description
Graph $G$	Arbitrary graph
Integer $k$	Desired clique size

Question:

Does $G$ contain a clique with at least $k$ vertices?

This problem is NP-complete. (en.wikipedia.org)

64.9 Maximum Clique Problem

The optimization version asks for:

\omega(G).

This problem is computationally difficult.

No polynomial-time algorithm is known for arbitrary graphs.

The problem is also difficult to approximate well.

Maximum clique is one of the standard benchmark problems in combinatorial optimization.

64.10 Clique Search Algorithms

Brute Force

Test every subset of vertices.

This requires:

2^{|V|}

subsets.

Backtracking

Recursive search prunes impossible extensions.

Branch-and-Bound

Upper bounds eliminate many search branches.

Heuristic Methods

Practical methods often use:

Method	Idea
Greedy search	Build dense subsets
Local improvement	Refine candidate cliques
Randomization	Explore search space

Exact algorithms remain exponential in worst case.

64.11 Bron-Kerbosch Algorithm

The Bron-Kerbosch algorithm is the classical recursive algorithm for enumerating maximal cliques. (en.wikipedia.org)

Main Idea

Maintain three sets:

Set	Meaning
$R$	Current clique
$P$	Possible extensions
$X$	Already processed vertices

The recursion systematically explores all maximal cliques.

Modern versions use pivoting for efficiency.

64.12 Cliques and Ramsey Theory

Ramsey theory studies unavoidable structure in large graphs.

A graph with many vertices must contain either:

Structure	Interpretation
Large clique	Strong density
Large independent set	Strong sparsity

The Ramsey number:

R(s,t)

is the smallest integer such that every graph with at least $R(s,t)$ vertices contains either:

Object	Size
Clique	$s$
Independent set	$t$

Clique theory therefore lies at the center of Ramsey theory.

64.13 Turán’s Theorem

Turán’s theorem determines the maximum number of edges in a graph avoiding large cliques.

Theorem 64.1. Turán’s Theorem

Among all graphs on $n$ vertices containing no clique of size:

r+1,

the graph with the maximum number of edges is the complete $r$ -partite balanced graph.

(en.wikipedia.org)

This theorem is foundational in extremal graph theory.

64.14 Cliques and Social Networks

In social network analysis, cliques represent groups where every member knows every other member.

Real social networks rarely contain large exact cliques because complete mutual interaction is difficult to maintain.

Instead, approximate clique structures are often studied.

Clique-based methods help detect tightly connected communities.

64.15 Clique Graphs

The clique graph of $G$ is constructed by:

Vertex in Clique Graph	Represents
A maximal clique of $G$	One clique

Two clique-vertices are adjacent if the corresponding maximal cliques intersect.

Clique graphs appear in structural graph theory and intersection graph theory.

64.16 Weighted Cliques

Suppose each vertex has weight:

w(v).

The weighted clique problem seeks a clique maximizing:

\sum_{v \in C} w(v).

Weighted cliques appear in:

Area	Interpretation
Bioinformatics	High-confidence interaction groups
Finance	Compatible investment clusters
Pattern recognition	Dense feature groups

64.17 Clique Polytope

Introduce variables:

x_v= \begin{cases} 1, & v \in C, \\ 0, & v \notin C. \end{cases}

The clique optimization problem becomes:

\max \sum_{v \in V} x_v

subject to:

x_u+x_v \le 1

for every nonedge:

uv \notin E.

These inequalities enforce pairwise adjacency among selected vertices.

The clique polytope is central in polyhedral combinatorics.

64.18 Perfect Graphs

A graph is perfect if:

\chi(H)=\omega(H)

for every induced subgraph $H$ .

Perfect graphs include:

Graph Class	Perfect?
Bipartite graphs	Yes
Chordal graphs	Yes
Interval graphs	Yes

Perfect graph theory studies graphs where clique and coloring structure align exactly.

64.19 Random Graphs

In random graphs:

G(n,p),

the clique number grows slowly relative to $n$ .

Typically:

\omega(G)

is logarithmic in $n$ when $p$ is fixed.

Random graph theory studies thresholds for clique emergence.

64.20 Applications

Cliques appear throughout mathematics and applications.

Application	Clique Meaning
Social networks	Mutual friendship groups
Bioinformatics	Strong interaction clusters
Scheduling	Compatible resource groups
Pattern recognition	Consistent feature sets
Communication systems	Fully connected subnetworks
Data mining	Dense association groups

The concept models complete pairwise compatibility.

64.21 Common Relationships

Parameters	Relation
Clique and independent set	$\omega(G)=\alpha(\overline{G})$
Clique and coloring	$\chi(G)\ge\omega(G)$
Triangle-free graphs	$\omega(G)\le2$

These identities connect density, sparsity, and coloring structure.

64.22 Exercises

Compute $\omega(P_7)$ .
Compute $\omega(C_5)$ .
Determine the clique number of $K_{4,7}$ .
Prove:

\omega(G)=\alpha(\overline{G}).

Show that every clique requires distinct colors in a proper coloring.
Give an example of a maximal clique that is not maximum.
Find all maximal cliques in a small graph.
Explain why triangle-free graphs satisfy:

\omega(G)\le2.

State Turán’s theorem in your own words.
Explain why the maximum clique problem is computationally difficult.