Smallest $k$ to make sure the $k$-nearest-neighbor graph is connected

Question

Given any $n$ points in $\mathbb{R}^d$, then make an undirected edge between every point and each of its $k$ nearest neighbors (in Euclidean distance). What is the smallest $k$ to make sure that the graph is (path) connected? I guess $k$ is a function of $n$, but it could also depend on $d$.

Answer 1

Cool Question. First, note that $k > \lfloor \frac{n}{2} -1 \rfloor$ since you can split the $n$ points into two "far apart" sets both having size size $\geq \lfloor \frac{n}{2}\rfloor$ yielding two disjoint graphs. To see that this is the worst case, apply dirac's theorem (any $n$ vertex graph with all degrees $ \geq n/2$ is Hamiltonian, and thus connected).