Generalised form Let $\cal G $ be a graph with $n $ vertices. Prove that Alice can determine, if $\cal G $ is connected or not by making $\frac {2n^2}{k} $ queries of form (is the distance $d(x,y)\le y $ or $d(x,y)> k $) for any vertices $x $ and $y $ Alice likes.

Key Lemma: In a graph $G$ with $n$ vertices, if there are $\frac{2n}{k}$ distinct vertices such that the distance between any two of them $\geq k$, then the graph is not connected. Proof: Suppose there are vertices $V_1, \ldots, V_p$, such that the distance between any two of them $\geq k$. Consider sets of vertices $S_i = \{V|V\in G, d(V, V_i)\leq [\frac{k-1}{2}]\}$. If $G$ is connected, then $|S_i| \geq [\frac{k+1}{2}]$ since there must be at least one vertex whose distance to $V_i$ equals $0, 1, \ldots, [\frac{k-1}{2}]$. Also, all sets are disjoint or else there exist $V_i$ and $V_j$ such that $d(V_i, V_j)<k$. Hence, there are at least $p\times [\frac{k+1}{2}]$ vertices in total, so $p\times [\frac{k+1}{2}]\leq n \Rightarrow p\leq \frac{n}{\lceil\frac{k}{2}\rceil}\leq \frac{2n}{k}$. Note that the last inequality is strict if $k$ is odd. If $k$ is even, then the distance between any two vertices in distinct sets is at least $2$. Since the graph is connected, there must be at least one vertex in none of the sets. So the inequality is also strict, hence $p<\frac{2n}{k}$. With the lemma above, we can see that the following algorithm works. Step 1: Choose any vertex $V_1$ to start. Ask the distance from $V_1$ to every other vertices. Step 2: We call a vertex "good" if we never get a $<k$ answer in a query associated with that vertex, and we get at least one $=k$ answer in a query associated with that vertex. If there are no good vertices left, the whole graph is connected if and only if we have got a $\leq k$ answer for all vertices. Else, choose any good vertex and ask the distance from it to every other vertex. Repeat this step. No matter the whole graph is connected or not, the algorithm can exactly spot all vertices in the connected component of $V_1$ in $n\times\frac{2t}{k}\leq\frac{2n^2}{k}$ queries, where $t$ is the size of the connected component of $V_1$. This is true by applying the lemma on $V_1$ and all the good vertices we have chosen to ask. Hence we're done.

Solution with p_square, Rg230403, Arwen713: Lemma: Let $S$ be a subset of the vertices of a simple, connected graph $G$ with $n$ vertices, such that any pair of vertices in $S$ are at a distance at least $k$ apart. Then $|S| \le \frac{2n-2}{k}$.

With the lemma above in mind, we provide an algorithm for Alice to know if the obvious graph associated with the question is connected or not in at most $\frac{2n^2}{k}$ steps: 0. Initialise a set $S$ to contain exactly one vertex $v_1$. 1. Query $v_{|S|}$ with every other vertex. 2. If every vertex in $V(G) \backslash S$ is at a distance less than $k$ from every vertex in $S$, then declare the graph connected and terminate the algorithm. 3. If some vertex in $V(G) \backslash S$ is at a distance $\ge k$ from every vertex in $S$ and $=k$ from at least one vertex in $S$, then call this vertex $v_{|S|+1}$ and put it in $S$ and go to step 1. Otherwise, declare the graph disconnected and terminate the algorithm.

Connectivity -> Trees, BFS trees, spanning trees. Assume $k\ge 5$, or this problem is trivial by toggling every edge. We consider a modified graph where we build a green edge between two vertices with distance $<k$, a red edge between two vertices with distance $=k$ and no edge otherwise. Lemma: The size of the maximal anticlique doesn't exceed $\frac{2n}{k}$. Proof: Consider a BFS-tree rooted at every anticlique with depth $\lfloor \frac{k+1}{2} \rfloor$ (root = depth 1) then note these BFS trees are disjoint, so we have at most $\frac{n}{k/2}$ roots. We proceed by this algorithm: Let $C$ be our anticlique containing $v_1$. Toggle every other vertex. If a vertex doesn't connect with any element of $C$, add it to $C$. If $|C| > \frac{2n}{k}$ we are done. Otherwise, we query every pair of vertices (u,v) st $u\in C, v\notin C$. Now each vertex in the anticlique is in a component of edges of a color. If there is one component, we win. Otherwise, if there is a component without red edges, we know the graph isn't connected because the BFS tree of the root has depth $k$ but there's gotta be other vertices, or there is only one component. Therefore, we obtain connected components $V_1, V_2, \cdots, V_j$ with no pairwise crossing edges. Since $|V_i|\ge k, j\le \frac nk$. Therefore, we take a vertex with a red edge from each $V_i$ and query each pair of vertices. If the modified graph still has two components, call $U_1, U_2$ where there are no crossing edges, where the roots are $r_1,s_1$ and the red vertices are $r_2,s_2$. (where the r's and the s's are in the same component in the modified graph) This implies the original graph is disconnected because if the graph is connected, and there is an edge between $XY$ then $\min\{ dist(r_1,s_1), dist(r_1,s_2), dist(r_2,s_1), dist(r_2,s_2)\}> k$. This implies $k$ is even and $dist(r_1,X)=dist(s_1,X)=dist(r_2,Y)=dist(s_2,Y)=\frac k2$. To address the connectivity, pick a vertex that is not the root or has a red edge would suffice, for a total of at most $\binom{2n/k}{2} + 2 \binom{n/k}{2} + (2n/k)(n-2n/k) < \frac{2n^2}{k}$ calls.