Probemos una afirmación más fuerte: existe un conjunto $W$ de no más de $2\sqrt{n}$ vértices tales que cada vértice en $V(G) \setminus W$ está conectado a algún vértice en $W$ (donde $V(G)$ es el conjunto de vértices del grafo $G$). Probemos esta afirmación por inducción. Un grafo de orden $1$ no cumple con las condiciones, por lo que el caso $n=2$ es la base.
-
Si $n=2$ entonces $W=V(G)$ y $|W|=2 \le 2\sqrt{2}$.
-
Supongamos que la afirmación es cierta para todos los grafos de orden a lo sumo $\ell$ y $|V(G)|=\ell+1$. Como has observado bien, si el grafo $G$ tiene un vértice $v$ con grado a lo sumo $2\sqrt{n}-1$ entonces $W=N[v]=N(v) \cup \{\,v\,\}$ es el conjunto deseado (donde $N(v)$ es el conjunto de todos los vértices adyacentes a $v$). Entonces, dejemos que cada vértice tenga un grado al menos de $2\sqrt{n}$. Luego podemos eliminar todos los vértices de $N[v]$ del grafo y considerar el grafo restante $G' = G(V(G) \setminus N[v])$. Por hipótesis de inducción, existe un conjunto $W' \subseteq V(G')$ de vértices tal que $|W'| \le \sqrt{n'}$, donde $n' \le n - (2\sqrt{n} + 1)$, y cada vértice de $G'$ está conectado a algún vértice de $W'$. Luego, $W = W' \cup \{\,v, u\,\}$, donde $u$ es algún vértice adyacente a $v$, es el conjunto tal que cada vértice de $G$ está conectado a algún vértice de $W$ y $$|W| = |W'| + 2 \le 2\sqrt{n'} + 2 \le 2\sqrt{n - 2\sqrt{n} - 1} + 2\le 2\sqrt{n}.$$ La última desigualdad se cumple ya que $$\left(\sqrt{n - 2\sqrt{n} - 1}\right)^2 = n - 2\sqrt{n} - 1 \le n - 2\sqrt{n} + 1 = (\sqrt{n} - 1)^2.$$
Por lo tanto, existe un conjunto deseado $W$ de no más de $2\sqrt{n} < \sqrt{n \log_2 n} + 1$ vértices para $n \ge 6$ y es fácil ver que existe un conjunto $W$ de no más de $\max\{\,2, n-1\,\} < \sqrt{n \log_2 n} + 1$ vértices para $2 \le n \le 5$.
P. D. Puedes utilizar cualquier base de logaritmo para $n$ suficientemente grande, sin embargo la afirmación puede ser incorrecta para valores pequeños de $n$.
