Clique

Definition

Let $G$ be a graph. 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 on $S$ is a complete graph. A set is a clique in $G$ if and only if it is an independent set in the complement graph. 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.