Maximal clique problem I understood what clique is all the nodes of the sub graph have to be connected to each other. In the following figure, it says that the maximal clique is {1,2,3,4,5}. But as per the definition of clique {1,2,3,4,5} is not a clique. Could someone explain this? 1 * * * * 2*******3 * * * * 4 5 * * * * * * 6 Consider the ***** as an edge.

Your understanding of clique is correct.
However the maximal clique in that graph is {1,2,3} and not {1,2,3,4,5}.
{1,2,3,4,5} is not even a clique in that graph.