Consider a simple regular graph on $n$ vertices and size $E$. How many distinct maximal independents can we find at the least in the graph? 


I think we can always find at least two maximal independent sets in the graph. This is an inspiration from the observation on bipartite graphs. In case of multipartite sets, the number could be always more, I think. Now, if the graph be $\chi$-partite, then, we can have a maximal indpendent set of size at least $\lfloor\frac{n}{\chi+1}\rfloor$. But, the number of such sets depends on the structure of the graph. I think we could have at least $\chi$ such sets, where the graph is assumed to be $\chi$ partite. Any lights on this? Thanks beforehand.



Number of maximal independent sets in a simple graph
Assume $G$ has chromatic number $χ$.
Let $a\_1,a\_2,...,a\_χ$ be a partition of $G$ into $χ$ independent sets (This is always possible given the chromatic number).


Every set $a\_k$ can be extended to a maximal independent set $A\_k$. The $A\_k$s are pairwise different. Otherwise, assume $A\_p=A\_q$, it follows that $a\_p \cup a\_q$ is independent, giving $G$ a coloring with $χ-1$ colors, which contradicts with the chromatic number of $G$ being $χ$.


So there exists at least $χ$ maximal independent sets. Complete $χ$-partite graphs have exactly this number of maximal independent sets.


