Edit: False as pointed by dgrozev.

I assume the algorithm can respond and adjust based on answers to earlier questions.

This is just detailed explanation of MellowMelon's beautiful solution. I wrote this because it takes some time for me to fully understand the solution. Consider the 64 cities as vertex of graphs. Possible number of edges are from $0$ to $\binom{64}{2} = 2016$. Now suppose that there exists an algorithm such that it can determine the connectedness of the graphs within less than 2016 questions. Fix such an algorithm. Assume that the algorithm is smart enough so that it gives no extra questions; that is when the algorithm stops, the final question is necessary. For convenience, let Y and N denotes the answer `Yes, there is an edge there' and `No, there is no edge there', respectively. Let $G_0$ be the graph with no edges. Applying the algorithm, we get several, say $t_0$, number of N answers and the algorithm ends with the conclusion `disconnected'. Now, let $G_1$ be the graph with one edge at the position where the algorithm halted on $G_0$. Applying the algorithm, we get $t_0-1$ number of N answers same with the case of $G_0$ but Y for $t_0$th question and several other N answers. The algorithm stops with the conclusion `disconnected' again. We continue with this procedure; add one edge for each $G_m$ to get $G_{m+1}$ where the algorithm halts with conclusion `disconnected'. This procedure cannot performed forever. At some point, we have $G_k$ which is really connected and the algorithm halts with the final answer Y with the conclusion `connected'. The graph obtained has several properties; $G_k$ is connected and the algorithm gets answer Y only when the nonexistence of that edge will witnesses the disconnectedness of the graph with the information before. Because of the assumption, when we apply the algorithm for $G_k$, there exists still vertices $A$ and $B$ such that the algorithm have not asked the existence of the edge $AB$. Because the algorithm have concluded the graph is actually connected, there exists a path from $A$ to $B$ whose edges consists of those which the algorithm asked before the existence. Let the edge $PQ$ be the last edge on the path, which the algorithm asked whose existence. The answer Y is contradictory since even if the existence of that edge is missing, we still have the possibility of existence of the edge $AB$ which prevents the disconnectedness of the graph. Hence, there does not exist such an algorithm.

anantmudgal09 wrote: ... Suppose that the pairs $\{(2,3),(3,4),\dots,(63,64),(64,1)\}$ are connected by a road. In this case, the graph is connected if and only if $(1,2)$ are connected. No, the graph is connected no matter whether $(1,2)$ are connected or not. MellowMelon wrote: ...The question which located the last edge on that path from $A$ to $B$ could not have received a yes answer because we still didn't know whether $AB$ existed at the time... But it might happen the question which located the last edge on that path from $A$ to $B$ must receive a "yes" answer, because that edge was also an edge of some other path, say from $C$ to $D$, that not depends whether $AB$ exists, and if a "no" answer were given then $C$ and $D$ would had been disconnected ?! I don't say your algorithm of answering "yes", only if it is the last chance of keeping the graph still connected, of being wrong. (In fact it is ok) but it needs more arguments. To prove no such algorithm exists, imagine it's a game between two players $A$ and $B$. $A$ asks questions about "are any two towns connected " and $B$ answers with "yes" or "not". Let $V_n$ denote a set of $n$ vertices (towns). We will prove that for any $n\geq 3$, $B$ has an algorithm $T_n$ of answering, following which, there will be needed no less than $n(n-1)/2$ (all possible) questions to determine whether the graph is connected, no matter what questions $A$ asks. It would mean $A$ could not have an algorithm to guess the connectivity with less than $n(n-1)/2$ questions. ("Formally speaking, any "algorithm" is defined by corresponding Turing machine.). One may think of that algorithm as if the actual graph is not fixed at the beginning. $B$ just answers the questions according to $T_n$, such that after $n(n-1)/2 -1$ rounds, there are two graphs $G_1(V_n, E_1)$ and $G_2(V_n, E_2)$ complying to the answers of $B$- one of them connected and the other- disconnected. The proof goes by induction. For $n=3$, the first two answers of $B$ are "yes" and "no", no matter what are the questions $A$ asks. After that there must be a third question, since there are two graphs complying to that answers- one connected and other disconnected. Let us suppose, we have constructed the algorithm $T_n$. Let's take $n+1$ vertices $V_{n+1}=\{v_1,v_2,\dots,v_{n+1}\}$. Denote $V' = \{v_2,v_3,\dots v_{n+1}\}$. Obviously $V'$ consists of $n$ vertices. We construct our algorithm $T_{n+1}$ in the following way. When $A$ asks whether two vertices among $V'$ are connected, $B$ triggers the algorithm $T_n$ applied to $V'$. If $A$ asks whether $v_1v_i$ are connected, $B$ answers "no", for all possible $n$ such questions, except to the last one pair $v_1v_k$ for which the answer is "yes". Let's follow that algorithm till it comes to the last pair of vertices in $V'$. If not all of the pairs $v_1,v_i, i=2,3,\dots,n+1$ are exhausted $B$ answers in such a way to make the graph spanned on $V'$ connected. After that it ensures that $A$ cannot guess till all $v_1v_i$ are exhausted. If on the other hand, all pairs $v_1,v_i, i=2,3,\dots,n+1$ are exhausted, the connectivity of $V_{n+1}$ is equivalent to the connectivity of $V'$, so the algorithm $T_n$ guarantees us $A$ cannot guess till all possible questions about pairs in $V'$ have been asked. Thus, the algorithm $T_{n+1}$ is constructed. Comment. Strictly speaking, the algorithm $T_n$ we've constructed is a finite automata, since it has a finite number of states: a subset of the set of all possible sets of pairs $v_iv_j$ and their answers and the input is some pair $v_kv_{\ell}$; after that the state changes as adding $v_kv_{\ell}$ and the corresponding answer. The Turing machines have more capabilities than the finite automata, since they have "infinite memory" and can have an "infinite output". For example there is no finite automata having as input $n$ (in its binary code) to output $n^2$.

Thanks to dgrozev for pointing out my errors in the previous posts.

dgrozev: You're right, that is a bit too implicit about how the disconnectedness works there. The missing argument: Let the last edge on the path from $A$ to $B$ be $XY$. If the path from $C$ to $D$ would have been broken by not including $XY$, then there is, WLOG, a path from $C$ to $X$ and a path from $D$ to $Y$. But there is also a path from $X$ to $A$ and a path from $Y$ to $B$ by the assumption that $XY$ could be the last edge on a path from $A$ to $B$. So we have a path from $C$ to $A$ and a path from $D$ to $B$. Thus if $XY$ is a potential edge on a path from $C$ to $D$, $AB$ is such an edge as well. anantmudgal: we're definitely not solving the same problem. It looks like you're assuming the algorithm cannot adjust to feedback from previous questions, and nothing in the problem indicates you should assume this. In your solution, the algorithm might realize what the graph is looking like from previous questions and ask about $(1,2)$ much earlier, so you cannot WLOG that.

Edit: Wrong. I now understand MellowMellon's Point. Sorry for the trouble!

That is not the issue. The issue is why you can WLOG that $(1,2)$ is the last edge asked about regardless of the rest of the graph. In fact you can prove that for the two graphs you propose, any algorithm that doesn't ask about edges it would never need to ask about will never use 2016 questions.

My solution was pretty much the same as that of @MellowMan above. But to make things easier for the checker, that is the to frame the solution, I made Fate and Hope play a game in which Hope had to guess the edges and Fate could manipulate the edge connectivity at each step the objective of the game same as the problem So I basically showed that Fate has a winning strategy. So suppose $A_1,A_2, \cdot ,A_n$ are the vertices of the graph. Hope asks questions about all the possible questions in her first $2015$ questions except about $A_{n-1}A_n$ But Fate using her moves, makes the graph such that only $A_iA_{i+1}$ are connected for $0<i<n-2$. So in the last question (which concerns $A_{n-1}A_{n}$), she can manipulate this edge (and hence the connectivity of the graph) and render Hope's any strategy hopeless. Hence Hope must ask at least $2016$ questions when $n=64$.

Note that this problem is essentially the same as IOI 2014 P3.

So wait... What was supposed to be the answer of the IOI problem ? We just have to write down the required strategy basically right ?

As in the IOI statement, let $n=64$, suppose we are Mei-Yu, and suppose Jian-Jia can answer each question based on previous questions. We give an explicit algorithm for Jian-Jia to force Mei-Yu to ask $\tbinom{n}{2}$ questions. Also, assume WLOG that Mei-Yu asks all $\tbinom{n}{2}$ questions, even if she can determine whether the graph is connected before asking all questions. After Mei-Yu asks a question, if at least one of the vertices Mei-Yu asks about is unlabeled, then label the vertices with the smallest positive integer(s) not yet used as a label (if both of the vertices asked about are unlabeled, label them in any order). Then, suppose the vertices are labeled $a$ and $b$, with $a>b$. Let Jian-Jia answer no if there exists a positive integer $c<a$ other than $b$ such that the existence of an edge between vertices labeled $a$ and $c$ is unknown. Otherwise, let Jian-Jia answer yes. We claim that this suffices. If Jian-Jia answers yes to a question between vertices labeled $a$ and $b$ with $a>b$, draw an arrow from the vertex labeled $a$ to the vertex labeled $b$. Suppose that the last question Mei-Yu asks is about vertices labeled $k$ and $l$, with $k>l$. From any vertex, if we keep following the arrows, we will land at either the vertex labeled $1$ or the vertex labeled $k$. Thus, the induced subgraphs containing the set of vertices that go to the vertex labeled $1$ and the set of vertices that go to the vertex labeled $k$ are the only two connected components. Also, notice that the vertex labeled $l$ must go to the vertex labeled $1$, so the graph is connected if and only if there exists an edge between the vertices labeled $k$ and $l$. $\square$

In fact, the situation is quite unyielding; the connectedness of the graph cannot be deduced in fewer than \(\binom{64}{2}\) inquiries even if it is known in advance to be acyclic. What follows is essentially MellowMelon's solution in post #3, just worded differently. Definition(s): Define a pargraph to entail the data of a triple \(\left(V\colon\textbf{Set},\ K\subseteq \binom{V}{2},\ E\subseteq K\right)\). Given such a pargraph \(\mathcal{H}=\left(V, K, E\right)\), call \(V\) its vertex set, \(K\) its domain, and \(E\) its edge set. If \(K=\binom{V}{2}\), then call \(\mathcal{H}\) total. Two pargraphs \(\mathcal{H}_{0}=\left(V_{0}, K_{0}, E_{0}\right)\) and \(\mathcal{H}_{1}=\left(V_{1}, K_{1}, E_{1}\right)\) are said to be consistent with one another iff \(V_{0}=V_{1}\) and \(E_{0}\cap K_{1}=E_{1}\cap K_{0}\). Of course, by forgetting \(K\), each pargraph \(\mathcal{H}=\left(V,K,E\right)\) becomes a graph (in the familiar sense) \(\mathcal{G}_{\mathcal{H}}:=\left(V,E\right)\) on \(V\). Call such \(\mathcal{G}_{\mathcal{H}}\) the minimal realization of \(\mathcal{H}\). If \(\mathcal{G}\) is total, we might also call its minimal realization its underlying graph. Clearly every pargraph is consistent with its minimal realization. Moreover, it's not hard to see that a given pargraph is consistent with a given total pargraph only if (but not necessarily if) the minimal realization of the former is a subgraph of the underlying graph of the latter. Finally, call a pargraph \(\mathcal{H}=\left(V, K, E\right)\) tree-pluripotent iff for all \(u\in \binom{V}{2}\setminus K\) it's the case that \(\mathcal{H}\) is consistent with a total pargraph whose underlying graph is a tree in which \(k\) occurs as an edge. (End Definition(s)) Proposition: Given a tree-pluripotent pargraph \(\mathcal{H}=\left(V, K, E\right)\) with \(K\subsetneq \tbinom{V}{2}\), the minimal realization of \(\mathcal{H}\) is disconnected. Proof: By hypothesis, there exists \(u\in \binom{V}{2}\setminus K\) and a total pargraph \(\widetilde{\mathcal{H}}=\left(V, \binom{V}{2}, \widetilde{E}\right)\) that is consistent with \(\mathcal{H}\) and whose underlying graph is a tree containing \(u\) as an edge. The minimal realization of \(\mathcal{H}\) is a subgraph of said tree that lacks at least one of said tree's edges (namely \(u\)), and is therefore disconnected, as claimed. \(\Box\) Proposition: Given a tree-pluripotent pargraph \(\mathcal{H}=\left(V, K, E\right)\) and \(u_{0}\in \binom{V}{2}\setminus K\), there exists a tree-pluripotent pargraph \(\widetilde{\mathcal{H}}=\left(V, K\sqcup \left\{u_{0}\right\}, \widetilde{E}\right)\) consistent with \(\mathcal{H}\). Proof: If every total pargraph consistent with \(\mathcal{H}\) whose underlying graph is a tree contains the edge \(u_{0}\), then \(\widetilde{\mathcal{H}}:=\left(V, K\sqcup \left\{u_{0}\right\}, \widetilde{E}\sqcup \left\{u_{0}\right\}\right)\) is the desired tree-pluripotent pargraph. On the other hand, if there exists some total pargraph \(\mathcal{H}'=\left(V,\binom{V}{2},E'\right)\) consistent with \(\mathcal{H}\) whose underlying graph is a tree not containing the edge \(u_{0}\), then we claim that \(\widetilde{\mathcal{H}}:=\left(V, K\sqcup \left\{u_{0}\right\}, \widetilde{E}\right)\) is the desired tree-pluripotent pargraph. Indeed, for any \(u\in \binom{V}{2}\setminus\left(K\sqcup\left\{u_{0}\right\}\right)\), the tree-pluripotency of \(\mathcal{H}\) implies the existence of a total pargraph \(\mathcal{H}''=\left(V,\binom{V}{2},E''\right)\) consistent with \(\mathcal{H}\) whose underlying graph is a tree containing the edge \(u\); it follows that there does not exist a path connecting the endpoints of \(u\) in the minimal realization of \(\mathcal{H}\). Thus for any \(u\) as above, if the edge \(u\) fails to occur in the underlying graph of \(\mathcal{H}'\), then we can nevertheless consider the (unique) path connecting its endpoints, delete from \(E'\) an edge in this path which does not belong to \(K\sqcup\left\{u_{0}\right\}\) (which necessarily exists by the above), and finally adjoin \(u\) to \(E'\) to obtain a total pargraph consistent with \(\widetilde{\mathcal{H}}\) whose underlying graph is a tree containing the edge \(u\). In other words, our constructed \(\widetilde{\mathcal{H}}\) is tree-pluripotent, as claimed. \(\Box\) In the context of the original question, we can identify the towns with elements of the set \(64:=\left\{0,\dots,63\right\}\) and interpret the state of our knowledge after some number of queries as the pargraph \(\mathcal{H}=\left(64,K,E\right)\), where \(K\) is the set of doubletons of towns between which we have inquired whether there exists a road and \(E\) is the subset of such inquiries that have been answered in the affirmative. It is clear that our knowledge suffices us precisely when either the underlying graph of any total pargraph consistent with \(\mathcal{H}\) is connected or the underlying graph of any total pargraph consistent with \(\mathcal{H}\) is disconnected. Suppose that we have asked \(K\subsetneq \binom{64}{2}\) questions. The empty pargraph \(\left(V,0,0\right)\) encoding our knowledge at the beginning of the investigation is manifestly tree-pluripotent, and thus by the latter Proposition our \(\mathcal{H}\) may well remain tree-pluripotent. But then (by definition and by the latter Proposition) this \(\mathcal{H}\) is then consistent with a total pargraph whose underlying graph is connected and a total pargraph whose underlying graph is disconnected. We conclude that there is no procedure that guarantees knowledge of the connectivity of the graph being probed in fewer than \(\binom{64}{2}=\boxed{2016}\) questions. \(\blacksquare\)