WOLFRAM

Wolfram Language & System Documentation Center

FindKClique[g,k]

finds a largest k-clique in the graph g.

FindKClique[g,k,n]

finds a k-clique containing at most n vertices.

FindKClique[g,k,{n}]

finds a k-clique containing exactly n vertices.

FindKClique[g,k,{nmin,nmax}]

finds a k-clique containing between nmin and nmax vertices.

FindKClique[g,k,nspec,s]

finds at most s k-cliques.

FindKClique[{g,v},k,…]

finds k-cliques that include the vertex v only.

FindKClique[{vw,…},…]

uses rules vw to specify the graph g.

Details
Details and Options Details and Options
Background & Context
Examples  
Basic Examples  
Scope  
Specification  
Enumeration  
Applications  
Properties & Relations  
See Also
Related Guides
History
Cite this Page

FindKClique

FindKClique[g,k]

finds a largest k-clique in the graph g.

FindKClique[g,k,n]

finds a k-clique containing at most n vertices.

FindKClique[g,k,{n}]

finds a k-clique containing exactly n vertices.

FindKClique[g,k,{nmin,nmax}]

finds a k-clique containing between nmin and nmax vertices.

FindKClique[g,k,nspec,s]

finds at most s k-cliques.

FindKClique[{g,v},k,…]

finds k-cliques that include the vertex v only.

FindKClique[{vw,…},…]

uses rules vw to specify the graph g.

Details

  • A k-clique is a maximal set of vertices that are at a distance no greater than k from each other.
  • FindKClique returns a list of k-cliques.
  • FindKClique will return an empty list if there is no k-clique.
  • FindKClique[…,k,nspec,All] finds all the k-cliques.
  • FindKClique works with undirected graphs, directed graphs, multigraphs, and mixed graphs.

Background & Context

  • FindKClique finds one or more k-cliques in a graph, returning them as a list of vertices. Here, a k-clique is a maximal set of vertices that are at a distance no greater than k from each other. k-cliques are used in project selection, pattern matching, finance, and network analysis.
  • FindKClique can be used to find k-cliques of different sizes, from 1 to the largest possible size (in general n for a graph on n vertices). FindKClique can be used to find a single k-clique of specified size, a specified number of cliques, or all.
  • 1-cliques are cliques. All k-clans are k-cliques, but the converse is not always true. Related functions include FindClique, FindKClan, FindKClub, and FindKPlex.

Examples

open all close all

Basic Examples  (2)

Find a largest 2-clique in a graph:

Wolfram Language code: g = [image];
Wolfram Language code: FindKClique[g, 2]

Show the 2-clique:

Wolfram Language code: HighlightGraph[g, Subgraph[g, %]]

Find all 4-cliques:

Wolfram Language code: g = ExampleData[{"NetworkGraph", "ZacharyKarateClub"}];
Wolfram Language code: FindKClique[g, 4, Infinity, All]

Scope  (14)

Specification  (8)

FindKClique works with undirected graphs:

Wolfram Language code: FindKClique[[image], 2]

Directed graphs:

Wolfram Language code: FindKClique[[image], 2]

Multigraphs:

Wolfram Language code: FindKClique[[image], 2]

Mixed graphs:

Wolfram Language code: FindKClique[[image], 2]

Find a largest 2-clique:

Wolfram Language code: FindKClique[[image], 2]

Find k-cliques for arbitrary k:

Wolfram Language code: Table[FindKClique[[image], k], {k, 1, 4}]

Use rules to specify the graph:

Wolfram Language code: FindKClique[{1 -> 2, 1 -> 5, 2 -> 3, 3 -> 4, 4 -> 5, 3 -> 6, 4 -> 6, 6 -> 3, 6 -> 4, 4 -> 3}, 2]

FindKClique works with large graphs:

Wolfram Language code: g = GridGraph[{10, 10, 10, 10}];
Wolfram Language code: FindKClique[g, 2]//Timing

Enumeration  (6)

A 2-clique containing exactly 4 vertices:

Wolfram Language code: FindKClique[[image], 2, {4}]

A 2-clique containing at most 4 vertices:

Wolfram Language code: FindKClique[[image], 2, 4]

A 2-clique containing between 3 and 5 vertices:

Wolfram Language code: FindKClique[[image], 2, {3, 5}]

A largest 2-clique that includes a given vertex:

Wolfram Language code: FindKClique[{[image], 6}, 2]

Find all 2-cliques in a graph:

Wolfram Language code: FindKClique[[image], 2, Infinity, All]

FindKClique gives an empty list if there is no k-clique:

Wolfram Language code: FindKClique[[image], 2, {3}]

Applications  (4)

Highlight all 2-cliques of size 5:

Wolfram Language code: g = PolyhedronData["Dodecahedron", "Skeleton"];
Wolfram Language code: Table[HighlightGraph[g, Subgraph[g, i]], {i, FindKClique[g, 2, {5}, All]}]

A friendship network between members of a karate club. Find the size of a largest group of people who are friends or a friend of a friend:

Wolfram Language code: g = ExampleData[{"NetworkGraph", "ZacharyKarateClub"}];
Wolfram Language code: Length[First[FindKClique[g, 2]]]

The largest such groups:

Wolfram Language code: FindKClique[g, 2, {%}, All]
Wolfram Language code: HighlightGraph[g, Subgraph[g, #]]& /@ %

A network of books linked by the same buyers on Amazon.com. Find a largest selection of books including The Clinton Wars that was frequently bought by buyers who previously bought a common book:

Wolfram Language code: g = ExampleData[{"NetworkGraph", "USPoliticsBooks"}];
Wolfram Language code: FindKClique[{g, "The Clinton Wars"}, 2]

To prevent data packets from circulating indefinitely in a mobile ad hoc network, a time to live (TTL—the maximum number of edges traversed) value is set to 3. Find all devices that can be reached from device 1:

Wolfram Language code: g = RandomGraph[SpatialGraphDistribution[100, 1, BinormalDistribution[{2, 1.5}, 0.8]]];
Wolfram Language code: FindKClique[{g, 1}, 3, Infinity]

Show the subnetwork:

Wolfram Language code: HighlightGraph[g, Subgraph[g, %]]

The best time to live for data packets:

Wolfram Language code: Max[GraphDiameter[Subgraph[g, #]] & /@ ConnectedComponents[g]] - 1

Unreachable devices:

Wolfram Language code: Complement[VertexList[g], First[FindKClique[{g, 1}, %, Infinity]]]

Properties & Relations  (8)

A k-clique in a graph g is a clique in the graph k^(th) power of g:

Wolfram Language code: g = [image];
Wolfram Language code: FindKClique[g, 2]
Wolfram Language code: FindClique[GraphPower[g, 2]]

A 1-clique is a clique:

Wolfram Language code: g = [image];
Wolfram Language code: FindKClique[g, 1]
Wolfram Language code: CompleteGraphQ[g, First[%]]

A complete graph is a maximum k-clique:

Wolfram Language code: CompleteGraph[10]
Wolfram Language code: FindKClique[%, 2]

A star graph is a maximum 2-clique:

Wolfram Language code: StarGraph[10]
Wolfram Language code: FindKClique[%, 2]

The (k-1)-clique is contained in a k-clique:

Wolfram Language code: g = [image];
Wolfram Language code: FindKClique[g, 1]
Wolfram Language code: FindKClique[g, 2, Infinity, All]

All k-clans are k-cliques. The converse is not always true:

Wolfram Language code: g = [image];
Wolfram Language code: FindKClan[g, 2, Infinity, All]
Wolfram Language code: FindKClique[g, 2, Infinity, All]

A k-club is contained in a k-clique:

Wolfram Language code: g = [image];
Wolfram Language code: FindKClub[g, 2]
Wolfram Language code: FindKClique[g, 2, 6]

The converse is not always true:

Wolfram Language code: FindKClique[{g, 6}, 2, 6]
Wolfram Language code: GraphDiameter[Subgraph[g, %]]

Find a largest 2-clique that includes a given vertex:

Wolfram Language code: g = [image];
Wolfram Language code: FindKClique[{g, 6}, 2]

Compare with 2-clan, 2-club, and 2-plex:

Wolfram Language code: FindKClan[{g, 6}, 2]
Wolfram Language code: FindKClub[{g, 6}, 2]
Wolfram Language code: FindKPlex[{g, 6}, 2]
Wolfram Research (2012), FindKClique, Wolfram Language function, https://reference.wolfram.com/language/ref/FindKClique.html (updated 2015).

Text

Wolfram Research (2012), FindKClique, Wolfram Language function, https://reference.wolfram.com/language/ref/FindKClique.html (updated 2015).

CMS

Wolfram Language. 2012. "FindKClique." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/FindKClique.html.

APA

Wolfram Language. (2012). FindKClique. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/FindKClique.html

BibTeX

@misc{reference.wolfram_2026_findkclique, author="Wolfram Research", title="{FindKClique}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/FindKClique.html}", note=[Accessed: 13-June-2026]}

BibLaTeX

@online{reference.wolfram_2026_findkclique, organization={Wolfram Research}, title={FindKClique}, year={2015}, url={https://reference.wolfram.com/language/ref/FindKClique.html}, note=[Accessed: 13-June-2026]}