Choosing subset of vertices connected to whole graph Consider a simple graph $G$ with $n$ vertices. For any two vertices, either they are connected by an edge, or there is a third vertex which is connected to both of them by an edge. (It is possible that both conditions hold.) Show that there exists a set $W$ of no more than $\sqrt{n\log n}+1$ vertices such that every vertex in $G$ is connected to some vertex in $W$.
If some vertex $u$ has degree $\leq \sqrt{n\log n}$, then the set of neighbors of $U$ can be seen to satisfy the condition. What if every vertex $u$ has degree $>\sqrt{n\log n}$?
 A: Let us prove more strong statement: there exists a set $W$ of no more than $2\sqrt{n}$ vertices such that every vertex in $V(G) \setminus W$ is adjacent to some vertex in $W$ (where $V(G)$ is the set of vertices of graph $G$). Let prove this statement by induction. Graph of order $1$ does not satisfy conditions, so case $n = 2$ is the base.


*

*If $n = 2$ then $W = V(G)$ and $|W| = 2 \le 2\sqrt{2}$.

*Suppose the statement holds for all graphs or order at most $\ell$ and $|V(G)| = \ell + 1$. As you noticed well if graph $G$ has a vertex $v$ of degree at most $2\sqrt{n} - 1$ then $W = N[v] = N(v) \cup \{\,v\,\}$ is desired set (where $N(v)$ is the set of all vertices adjacent to $v$). So let each vertex has degree at least $2\sqrt{n}$. Then we can remove all vertices of $N[v]$ from graph and consider remaining graph $G' = G(V(G) \setminus N[v])$. By induction hypothesis there exists a set $W' \subseteq V(G')$ of vertices such that $|W'| \le \sqrt{n'}$, where $n' \le n - (2\sqrt{n} + 1)$, and each vertex of $G'$ is adjacent to some vertex of $W'$. Then $W = W' \cup \{\,v, u\,\}$, where $u$ is some vertex adjacent to $v$, is the set such that each vertex of $G$ is adjacent to some vertex of $W$ and
$$|W| = |W'| + 2 \le 2\sqrt{n'} + 2 \le 2\sqrt{n - 2\sqrt{n} - 1} + 2\le 2\sqrt{n}.$$ 
The last inequality holds since
$$\left(\sqrt{n - 2\sqrt{n} - 1}\right)^2 = n - 2\sqrt{n} - 1 \le n - 2\sqrt{n} + 1 = (\sqrt{n} - 1)^2.$$
It follows that there exists a desired set $W$ of no more than $2\sqrt{n} < \sqrt{n \log_2 n} + 1$ vertices for $n \ge 6$ and it is easy to see that there exists a set $W$ of no more than $\max\{\,2, n-1\,\} < \sqrt{n \log_2 n} + 1$ vertices for $2 \le n \le 5$.
P. S. You may use any base of logarithm for large enough $n$ however the statement may become wrong for small $n$.
