2
$\begingroup$

Hardly I can not find the clear differences between Maximal and Maximum Cliques, As I think Maximal means a graph can not be extended to connect more edges , means each node is connected with all other nodes, but is Maximum means at least a graph should be connected to other graph ? any suggestion please

$\endgroup$
5
$\begingroup$

Maximum means that there is no larger clique in the graph. Maximal mean that the given clique cannot be extended to a larger one.

As an example, consider $G=K_{3}\cup K_{4}$ the disjoint union of two cliques. The size of the largest clique in the graph is $4$ and the $K_4$ is a maximum sized clique. The $K_{3}$ is maximal, meaning that if you add any other vertex in $G$ to the $K_{3}$ you no longer have a clique. But it is not maximum since the size of it is $3<4$.

$\endgroup$
6
  • $\begingroup$ @user253008, no problem. I got these backwards all the time for a long time (and still doubt myself periodically). $\endgroup$
    – TravisJ
    May 26 '15 at 19:49
  • $\begingroup$ Yah, you are right, But if we add a node to K3, you said we will no longer have a clique so what then we have in this case?. and why Finding the maximum clique in a graph is NP-hard Problem ? $\endgroup$ May 26 '15 at 19:51
  • $\begingroup$ @user253008, Finding a maximal clique is not hard... add vertices one at a time until you can't. Finding the largest possible clique is hard (not in this particular case). $\endgroup$
    – TravisJ
    May 26 '15 at 19:54
  • $\begingroup$ OK, OK Again please :But if we add a node to K3, you said we will no longer have a clique so what then we have in this case $\endgroup$ May 26 '15 at 20:00
  • $\begingroup$ Can someone give me an example about non-maximal clique ? please and why ? $\endgroup$ May 26 '15 at 22:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.