An independent set is a set of vertices in a graph, no two of which are adjacent. A maximal independent set is an independent set that you can not add any vertex. I want to know if the number of all maximal independent set is an exponential number.


Yes, consider the graph that consists of vertices $v_1,\ldots,v_{2n}$ and edges $(v_1,v_2),(v_3,v_4),\ldots,(v_{2n-1},v_{2n})$. This graph has exactly $2^n$ maximal independent sets, because for each $0\leq i\leq n-1$, we can either choose the vertex $v_{2i}$ or $v_{2i+1}$.

  • $\begingroup$ Please can give me a reference $\endgroup$
    – tounsy
    Dec 17 '14 at 10:22
  • 1
    $\begingroup$ @A.Schulz No, that graph would only have 1 maximal independent set, since any independent set that does not contain all vertices can be extended by adding another vertex, so it is not maximal. $\endgroup$ Dec 17 '14 at 10:22
  • $\begingroup$ But if you take the graph with no edges and n vertices we have one maximal independent set that is the set with all vertices ? $\endgroup$
    – tounsy
    Dec 17 '14 at 10:25
  • 4
    $\begingroup$ @tounsy No, it does have $2^n$ maximal independent sets. The graph consists of $n$ components and each component is two vertices connected by a single edge. For each component of the graph, I can pick either endpoint of the edge to be in the independent set. $\endgroup$ Dec 17 '14 at 10:30
  • 3
    $\begingroup$ @tounsy That bound would be obtained by using $n/3$ triangles in place of Tom's $n/2$ edges. Also, note that you are expected to do some research before asking questions here so you should probably have found the Moon-Moser bound when you did that. $\endgroup$ Dec 17 '14 at 10:46

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.