# The number of maximal independent sets

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}$.
• @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. Dec 17 '14 at 10:30
• @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. Dec 17 '14 at 10:46