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 **every** maximal 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$.



Dense graphs where every maximal independent set is large
No, the object you’re looking for does not exist.


A result of Harutyunyan, Horn, and Verstraete (see Theorem 4.15 of [this survey](https://www.sciencedirect.com/science/article/pii/S0012365X13000083#br000305)) states the following



> 
> **Theorem:** There is a constant $c > 0$ such that every $d$-regular graph $G$ on $n$ vertices of girth at least 5 satisfies $i(G) \leq \dfrac{n(\log(d)+c)}{d}$.
> 
> 
> 


Here, $i(G)$ is the independence domination number, which is the size of the smallest maximal independent set.


Setting $m=n^{1+\varepsilon}$, this bound gives $i(G) \leq O(n^{1-\varepsilon} \log(n)) = o(n)$.


