cover image

Clique (graph theory)

Adjacent subset of an undirected graph / From Wikipedia, the free encyclopedia

Dear Wikiwand AI, let's keep it short by simply answering these key questions:

Can you list the top facts and stats about Clique (graph theory)?

Summarize this article for a 10 year old

SHOW ALL QUESTIONS

In the mathematical area of graph theory, a clique (/ˈklk/ or /ˈklɪk/) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph is an induced subgraph of that is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph (the clique problem) is NP-complete, but despite this hardness result, many algorithms for finding cliques have been studied.

VR_complex.svg
A graph with
  • 23 × 1-vertex cliques (the vertices),
  • 42 × 2-vertex cliques (the edges),
  • 19 × 3-vertex cliques (light and dark blue triangles), and
  • 2 × 4-vertex cliques (dark blue areas).
The 11 light blue triangles form maximal cliques. The two dark blue 4-cliques are both maximum and maximal, and the clique number of the graph is 4.

Although the study of complete subgraphs goes back at least to the graph-theoretic reformulation of Ramsey theory by Erdős & Szekeres (1935),[1] the term clique comes from Luce & Perry (1949), who used complete subgraphs in social networks to model cliques of people; that is, groups of people all of whom know each other. Cliques have many other applications in the sciences and particularly in bioinformatics.

Oops something went wrong: