7
$\begingroup$

I'm unable to understand what maximal clique is. I mean how a clique can't be extended by a node and remain a clique? If I add a node and then I connect this node to every other nodes in the clique, then it got extended and remained a clique!

$\endgroup$
4
  • $\begingroup$ The issue is whether or not the node and edges you just added are already present in your graph. If they are, then you can extend. If not, then you cannot. $\endgroup$
    – wckronholm
    Apr 17 '14 at 19:59
  • $\begingroup$ Consider a graph that looks like this $\bullet - \bullet - \bullet$. The first edge is a clique $K_2$ but if you add the third node, it's not a clique anymore. $\endgroup$ Apr 17 '14 at 20:01
  • $\begingroup$ You're right; it only makes sense to talk about a maximal clique in a particular graph. There is no absolute maximal clique. This is analogous to the way a number may be maximal in a particular set even though there is no globally maximal number. $\endgroup$
    – MJD
    Apr 17 '14 at 20:03
  • $\begingroup$ @NajibIdrissi what's the difference between a clique and a maximal clique then from your example? If you add the third node it won't be even a clique $\endgroup$
    – Jack Twain
    Apr 17 '14 at 20:12
20
$\begingroup$

The phrase "maximal clique" is usually used in terms of a subgraph of a given graph $G$. So a subgraph $H$ of a graph $G$ is a maximal clique in $G$ if $H$ is isomorphic to a complete graph and there is no vertex $v \in V(G)\backslash V(H)$ so that $v$ is adjacent to each vertex of $H$.

In other words, a subgraph $H$ of a graph $G$ is a maximal clique in $G$ if $H$ is a clique (there is an edge between every pair of vertices in $H$) and there is no vertex in $G$ but not in $H$ that sends an edge to every vertex of $H$. So you couldn't create a bigger clique in $G$ by adding another vertex to $H$.

enter image description here

The red subgraph of the first graph is not a clique because there are two vertices in it not connected by an edge. The red subgraph of the second graph is a clique, but because there is a vertex in the larger graph connected to all 3 vertices in the subgraph, it is not a maximal clique. The red subgraph of the third graph is a maximal clique because it is a clique, and the last vertex not included in the subgraph does not send an edge to every vertex in the subgraph. The red subgraph of the fourth graph is a maximal clique because it is a clique, and neither of the vertices not included in the subgraph send an edge to every vertex in the subgraph. Note that the third and fourth red subgraphs are both maximal cliques even though the the third red subgraph is larger.

$\endgroup$
6
  • $\begingroup$ I'm sorry but your answer is a bit too advance for me. Can you post figures that explain the idea? $\endgroup$
    – Jack Twain
    Apr 17 '14 at 20:05
  • $\begingroup$ I couldn't understand "if H is isomorphic to a complete graph" $\endgroup$
    – Jack Twain
    Apr 17 '14 at 20:05
  • $\begingroup$ also couldn't understand the notation: v∈V(G)∖V(H) $\endgroup$
    – Jack Twain
    Apr 17 '14 at 20:05
  • $\begingroup$ @AlexTwain I added some more explanation. See if it is clear now. $\endgroup$ Apr 17 '14 at 20:21
  • 1
    $\begingroup$ Perhaps it should be noted that the top triangle of the example graph is a maximal clique too, even though it is smaller in size than the maximal clique already pointed out. $\endgroup$ Apr 17 '14 at 21:05

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.