Maximal clique problem

243 Views Asked by At

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.

2

There are 2 best solutions below

0
On BEST ANSWER

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.

0
On

A clique of a graph is a subset of the vertices with the property that each vertex of this subset is adjacent to every other vertex of the subset (complete induced subgraph)