# Chapter 64. Cliques

# 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](https://en.wikipedia.org/wiki/Clique_%28graph_theory%29?utm_source=chatgpt.com))

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](https://en.wikipedia.org/wiki/Clique_problem?utm_source=chatgpt.com))

## 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](https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm?utm_source=chatgpt.com))

### 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](https://en.wikipedia.org/wiki/Tur%C3%A1n%27s_theorem?utm_source=chatgpt.com))

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

1. Compute \(\omega(P_7)\).

2. Compute \(\omega(C_5)\).

3. Determine the clique number of \(K_{4,7}\).

4. Prove:

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

5. Show that every clique requires distinct colors in a proper coloring.

6. Give an example of a maximal clique that is not maximum.

7. Find all maximal cliques in a small graph.

8. Explain why triangle-free graphs satisfy:

$$
\omega(G)\le2.
$$

9. State Turán's theorem in your own words.

10. Explain why the maximum clique problem is computationally difficult.