Prove that the problem of determining whether a graph is connected is evasive

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

1. Suppose M is an algorithm that makes m < (n C 2) queries to decide whether the graph is connected
2. 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
3. After all m queries, there are
   • responses for previously queried edges, which can be 1 or 0
   • one unqueried edge that is unknown
4. 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)
5. M cannot distinguish between G0 and G1 because both are consistent with its queries.
6. 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.
7. 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)
8. 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.