Question about FindKClique

Question

Say we have a graph:

g = CompleteGraph[5];

and that we want to find all the triangles in g. I tried to use FindKClique, in the following way:

FindKClique[g,1,{3},All]

but it returns an empty list and I am not sure why. I must be misunderstanding something about FindKClique but I'm not sure what it is. The output I would expect to get is the following:

Map[First,FindCycle[g,{3},All],{2}]

{{3, 2, 4}, {3, 5, 4}, {1, 5, 3}, {2, 3, 5}, {2, 4, 5}, {1, 5, 2}, {1, 3, 2}, {1, 2, 4}, {1, 3, 4}, {1, 5, 4}}

Can someone explain why FindKClique is not doing what I thought it would?

Answer 1

From the docs of FindKClique,

A k-clique is a maximal set of vertices that are at a distance no greater than k from each other.

There are no maximal cliques that are 3-cliques in $K_5$.

I suggest you use IGCliques from IGraph/M, which finds all cliques, not just maximal ones.

<< IGraphM`

IGCliques[CompleteGraph[5], {3}]
(* {{3, 4, 5}, {2, 3, 4}, {2, 3, 5}, {2, 4, 5}, {1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, {1, 4, 5}} *)

If you only need triangles (not larger cliques), you can also use IGTriangles, which is going to be faster.

IGTriangles[CompleteGraph[5]]
(* {{1, 2, 5}, {1, 2, 3}, {1, 2, 4}, {1, 3, 5}, {1, 3, 4}, {1, 4, 5}, {2, 3, 5}, {2, 3, 4}, {2, 4, 5}, {3, 4, 5}} *)

If you need to find sets of vertices no more than distance $k$ away, as with FindKClique, first connect each vertex to its $k$-neighbourhood, then find normal cliques.

IGCliques[IGConnectNeighborhood[graph, k], {size}]