# FindClique

FindClique[g]

finds a largest clique in the graph g.

FindClique[g,n]

finds a clique containing at most n vertices.

FindClique[g,{n}]

finds a clique containing exactly n vertices.

FindClique[g,{nmin,nmax}]

finds a clique containing between nmin and nmax vertices.

FindClique[g,nspec,s]

finds at most s cliques.

FindClique[{g,v},]

finds cliques that include the vertex v only.

FindClique[{vw,},]

uses rules vw to specify the graph g.

# Details • A clique is a maximal set of vertices where the corresponding subgraph is a complete graph.
• FindClique returns a list of cliques.
• FindClique will return an empty list if there is no clique.
• FindClique[,nspec,All] finds all the cliques.
• For weighted graphs, FindClique gives a set of vertices with maximum sum of vertex weights.
• FindClique works with undirected graphs, directed graphs, weighted graphs, multigraphs, and mixed graphs.

# Background & Context

• FindClique finds a set of maximal cliques of specified size in a graph, returned as a list of vertex lists. Here, a clique is a subset of vertices such that the corresponding induced subgraph is a complete graph. Cliques are used in project selection, pattern matching, finance, and network analysis. In general, FindClique[g,nspec,s] finds a set of s maximal cliques of specified size nspec in a graph g.
• There are two especially important types of cliques: maximum and maximal. Note these are not equivalent. A maximum clique is a clique containing the largest possible number of vertices for a given graph. In contrast, a maximal clique set is a clique that cannot be extended by including one more adjacent vertices, meaning it is not a subset of a larger clique. A maximum clique is therefore always maximal (since it obviously cannot be extended if it is already of the maximum size), but the converse is not necessarily true. To confuse the terminology even more, some authors refer to maximum cliques simply as "cliques".
• FindClique can find maximal cliques of different sizes. FindClique can also find a single maximal clique of specified size, a specified number of cliques, or all such cliques.
• FindClique[g] finds a single maximum clique of a graph g, FindClique[g,Length/@FindClique[g],s] finds at most s, and FindClique[g,Length/@FindClique[g],All] finds all such cliques. The size of a maximum clique of a graph g is known as its clique number, and the problem of finding the size of a maximum clique for a given graph is NP-complete, meaning computation can be exponentially slow.
• finds a single maximal clique of a graph g, FindClique[g,Infinity,s] finds at most s, and finds all such cliques. Maximal cliques are important in graph theoretic applications, including graph coloring and fractional graph coloring.
• Not-necessarily-maximal cliques cannot be found directly using FindClique but can be simplistically enumerated by taking the union over the collection of all subsets of all maximal cliques.
• A maximal independent vertex set (which can be found using FindIndependentVertexSet) of a graph is equivalent to a maximal clique on its GraphComplement. A collection of vertices vlist of a graph g can be tested to see if it is a clique (without the requirement that it also be maximal) using CompleteGraphQ[g,vlist]. FindKClique, FindKClan, and FindKClub find clique-like structures that allow less-than-complete connections in subgraphs.

# Examples

open all close all

## Basic Examples(2)

Find a largest clique in a graph:

 In:= In:= Out= Show the clique:

 In:= Out= Find all cliques:

 In:= In:= Out= ## Properties & Relations(8)

Introduced in 2010
(8.0)
|
Updated in 2015
(10.3)