maximum number of maximal independent set in a graph with n vertices

Question

Is it always true that for any connected graph G with n vertices, the maximum number of maximal independent set is at most n?

Answer 1

No.

A concrete example: Let $P$ be the 8-vertex path $P=u_1u_1\ldots u_8$. Then $\{u_1,u_3,u_5,u_7\}$, $\{u_1,u_4,u_6,u_8\}$, $\{u_1,u_3,u_6,u_8\}$, $\{u_1,u_3,u_5,u_8\}$, $\{u_1,u_4,u_7\}$, $\{u_2,u_4,u_6,u_8\}$, $\{u_2,u_5, u_8\}$, $\{u_2,u_4, u_7\}$,$\{u_2,u_5, u_7\}$ are all maximal independent sets in $P$ and there just listed are $9>8$ such sets.

In fact for a path $P_n$ on $n$ vertices; $n$ large, there are an exponential number (in $n$) of maximal independent sets.