# Complete Graph & Connected Component

There seems to be various implementations of algorithms that find the connected components of a graph.

I have not found, however, an algorithm or implementation for finding which of the connected components are also complete. Does anybody know of one?

Thank you!

• You don't need a special algorithm. Given a connected component, just check that all the edges are there. – Yuval Filmus Jun 25 '17 at 2:09
• Implementations are off-topic here. – Yuval Filmus Jun 25 '17 at 2:09

Most graph libraries will find the connected components of a graph G as a list of connected subgraphs [H1, H2, H3, ...] and most of these libraries will have the functionality to obtain the number of nodes and number of edges in a graph. Assuming H is a simple graph (no loops, no multiple edges) with m edges and n vertices, one can say it is complete if

m == n*(n-1)/2


So, given the output of connected components, you should do:

for each graph H in [H1, H2, ...]
int n = H.getNumVertices()
int m = H.getNumEdges()
if (n*(n-1) == 2*m)
state that H is complete
else
state that H is not complete

• It should be noted that the equality is valid only for simple graphs (no loops, no multiple edges) . – anr Jun 28 '17 at 21:28

Though the answer is already posted, here I propose a beatiful approach. One can notice that a graph is union of cliques if and only if it doesn't contain a path on 3 vertices, $P_3$, as induced subgraph. It looks like a triangle without one side. Just checking the adjacency matrix for $a_{ij}+a_{ik}+a_{jk}=2$ will be sufficient. It's $O(n^3)$.

• I don't think the OP wants to decide if all components are cliques. they want to obtain all clique-components. – Raphael Jun 29 '17 at 5:11