P.S. My proof attempt/rewrite based on the solution discussed, uploaded mainly for my own reference. (warning: possibly erroneous)
Claim: The problem of determining whether a graph is connected is evasive
 evasive as in it requires n C 2 queries i.e checking all the edges
 Prove by making an adversary argument
 Suppose M is an algorithm that makes m < (n C 2) queries to decide whether the graph is connected
 The adversary responds to each query as follows:
 suppose it receives the x th query for
1 <= x <= m
 it considers the graph x defined by taking
 all the responses before this query (those that have reply of 1 => those edges that exist)
 all unqueried edges are set to 1 and hence considered as exist
 the current queried edge is set to 0 and hence not included
 if this graph is still connected without the current edge, then the adversary replies 0, else replies 1
 it's like if the graph does not need the current edge to be fully connected, then return 0
 suppose it receives the x th query for
 After all m queries, there are
 responses for previously queried edges, which can be 1 or 0
 one unqueried edge that is unknown
 The adversary makes two graphs using the above information:
 G0: take all edges that are connected according to the responses + set the unqueried edge to 0 (ignore the unknown edge)
 G1: take all edges that are connected according to the responses + set the unqueried edge to 1 (include the unknown edge)
 M cannot distinguish between G0 and G1 because both are consistent with its queries.
 The argument is that G0 is disconnected while G1 is connected, and hence since M can only decide whether the graph is connected or not, M must be wrong for one of the above inputs.
 G1 is connected trivially because it is consistent with the adversary's response strategy.
 If you set the unqueried edges to 1, then the graph must be connected (together with those edges that exist, i.e. previously answered 1)
 G0 is disconnected by contradiction:
 Suppose G0 is connected for purpose of contradiction
 Then let (i, j) = the last unqueried pair of nodes be connected, i.e there is a path between i and j
 Given the adversary strategy, it must replied 1 to all edges on this path, because they exist
 let (i', j') be the edge on this path that was queried last. Then the adversary should have answered 0 as i and j will be set as connected since they are unqueried at that point.
 So a contradiction arises and the assumption is incorrect.
Concrete Example

n = 3

Since the algorithm is going to decide whether the graph is connected or not, the adversary simply takes the input that is not consistent with the algorithm.