Skip to main content
1 of 4
user avatar
user avatar

Vertex cover of regular graph

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$?

user76479