**(1.)** How small can set $S$ of vertices in any regular undirected graph $G$ on $n$ vertices with degree $\Omega(n^\alpha)$ where $\alpha\in(0,1)$ can be such that every edge in the graph is incident on at least one vertex in $S$? For instance is $|S|\leq\frac nc$ always possible with some fixed $c>1$ (say $c=2$)?


**(2.)** Moreover consider the subgraph $G\_S$ with vertex set $S$ and edge set consisting of edges in $G$ with both end points in $S$. Can we pick an $S$ such that subgraph $G\_S$ is regular? What is the least degree that $G\_S$ can have?


So in essence what is the product of least degree and minimal cardinality possible for $G\_S$?



Vertex cover of regular graph
The complement of $S$ is an independent set, so the minimum value of $|S|$ is $n-\alpha(G)$ where $\alpha(G)$ is the size of the largest independent set. For non-complete connected regular graphs of degree $r$, there is an independent set of size $n/r$ since the chromatic number is at most $r$. So you can find $S$ with $|S|\le n(1-1/r)$. For complete graphs obviously $|S|=n-1$ is the best you can do.


