A *maximal independent set* of a graph $G$ is a subset of vertices $S$ such that each vertex of $G$ is either in $S$ or adjacent to some vertex in $S$, and no two vertices in $S$ are adjacent. Consider graphs of $n$ nodes that are dense, i.e., there are $m$ edges, where $m \ge n^{1+\epsilon}$, for some constant $\epsilon>0$.

**Update:**
As pointed out in the comments, one can take $n/2$ isolated vertices and then any dense graph of high $\ge 5$ on the remaining $n/2$ vertices. However, I'm more interested in **regular** graphs where every node has the same degree. I've updated my question is as follows:

Does there exist a family of regular dense graphs of girth $\ge 5$ where

everymaximal independent set has a size of at least $\Omega(n)$?

Note that the girth $\ge 5$ condition rules out obvious candidates such as the complete bipartite graph which has girth $4$.

regulargraphs. I've updated the question. $\endgroup$ – wandering_lambda Apr 20 at 2:01