---
tag: 0G52BPNPKG
kind: definition
name: Clique
msc: [05C69]
defines: 0BYX1D7C2E
sources:
  - url: https://en.wikipedia.org/wiki/Clique_(graph_theory)
    locator: Definitions
---

## Definition

Let $G$ be a [[graph|0JD5C82QMB]].
A clique in $G$ is a set $S$ of vertices of $G$ such that any two distinct vertices of $S$ are adjacent.

## Remarks

A set $S$ is a clique if and only if the [[induced subgraph|0V05FC4GKQ]] on $S$ is a [[complete graph|03WKB2H474]].
A set is a clique in $G$ if and only if it is an [[independent set|0KZJ82WEPP]] in the [[complement graph|0RNMP6VCR2]].
To decide whether a graph has a clique of a given size is an NP-complete problem.

## Explanations

### L1 human

A clique is a group of vertices that are all joined to each other.
In a social network, it is a group of people who all know each other.