Is there a set $S$ of $O(n^{1-\alpha})$ vertices in any regular undirected graph $G$ on $n$ vertices with degree $\Omega(n^\alpha)$ where $\alpha\in(0,1)$ such that every edge in the graph is incident on at least one vertex in $S$?
1 of 4
Vertex cover of regular graph
user76479