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.